TY - GEN

T1 - Parameterized algorithms for generalized domination

AU - Raman, Venkatesh

AU - Saurabh, Saket

AU - Srihari, Sriganesh

PY - 2008/9/22

Y1 - 2008/9/22

N2 - We study the parameterized complexity of a generalization of Dominating Set problem, namely, the Vector Dominating Set problem. Here, given an undirected graph G∈=∈(V,E), with V∈=∈{v 1, ∈⋯∈, v n }, a vector and an integer parameter k, the goal is to determine whether there exists a subset D of at most k vertices such that for every vertex v∈ ∈V ≥ D, at least l(v) of its neighbors are in D. This problem encompasses the well studied problems - Vertex Cover (when l(v)∈=∈d(v) for all v∈ ∈V, where d(v) is the degree of vertex v) and Dominating Set (when l(v)∈=∈1 for all v∈ ∈V). While Vertex Cover is known to be fixed parameter tractable, Dominating Set is known to be W[2]-complete. In this paper, we identify vectors based on several measures for which this generalized problem is fixed parameter tractable and W-hard. We also show that the Vector Dominating Set is fixed parameter tractable for graphs of bounded degeneracy and for graphs excluding cycles of length four.

AB - We study the parameterized complexity of a generalization of Dominating Set problem, namely, the Vector Dominating Set problem. Here, given an undirected graph G∈=∈(V,E), with V∈=∈{v 1, ∈⋯∈, v n }, a vector and an integer parameter k, the goal is to determine whether there exists a subset D of at most k vertices such that for every vertex v∈ ∈V ≥ D, at least l(v) of its neighbors are in D. This problem encompasses the well studied problems - Vertex Cover (when l(v)∈=∈d(v) for all v∈ ∈V, where d(v) is the degree of vertex v) and Dominating Set (when l(v)∈=∈1 for all v∈ ∈V). While Vertex Cover is known to be fixed parameter tractable, Dominating Set is known to be W[2]-complete. In this paper, we identify vectors based on several measures for which this generalized problem is fixed parameter tractable and W-hard. We also show that the Vector Dominating Set is fixed parameter tractable for graphs of bounded degeneracy and for graphs excluding cycles of length four.

UR - http://www.scopus.com/inward/record.url?scp=51849139849&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-85097-7_11

DO - 10.1007/978-3-540-85097-7_11

M3 - Conference contribution

AN - SCOPUS:51849139849

SN - 3540850961

SN - 9783540850960

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 116

EP - 126

BT - Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings

ER -