Parameterized complexity of generalized domination problems

详细信息	查看全文 | 推荐本文 |

• 作者：Petr A. Golovach^a ; ^{petr.golovach@durham.ac.uk} ; Jan Kratochví ; l^b ; ^{honza@kam.mff.cuni.cz} ; Ond艡ej Suchý ; ^b ; ^{suchy@kam.mff.cuni.cz}
• 关键词：Generalized domination ; Parameterized complexity ; Even set ; Odd set
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：April, 2012
• 卷：160
• 期：6
• 页码：780-792
• 文件大小：376 K

摘要

Given two sets of non-negative integers, a set of vertices of a graph is -dominating if for every vertex , and for every . This concept, introduced by Telle in 1990鈥檚, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of -domination in this general setting. Among other results, we show that the existence of a -dominating set of size (and at most ) are W[1]-complete problems (when parameterized by ) for any pair of finite sets and . We further present results on dual parameterization by , and results on certain infinite sets (in particular for being the sets of even and odd integers).