Parameterized algorithms for generalized domination

Venkatesh Raman, Saket Saurabh, Sriganesh Srihari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
Pages116-126
Number of pages11
DOIs
Publication statusPublished - 22 Sep 2008
Event2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 - St. John's, NL, Canada
Duration: 21 Aug 200824 Aug 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5165 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
CountryCanada
CitySt. John's, NL
Period21/08/0824/08/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this