Parameterized dominating set problem in chordal graphs: complexity and lower bound

Chunmei Liu () and Yinglei Song ()
Additional contact information
Chunmei Liu: Howard University
Yinglei Song: University of Maryland Eastern Shore

Journal of Combinatorial Optimization, 2009, vol. 18, issue 1, No 6, 87-97

Abstract: Abstract In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time $|V|^{o({\sqrt{k}})}$ unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to $O(2^{\sqrt{k}}|V|^{2\sqrt{k}})$ when the underlying graph G is an interval graph.

Keywords: Chordal graphs; Dominating set; Parameterized complexity; Lower bound; Interval graphs (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9141-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:18:y:2009:i:1:d:10.1007_s10878-008-9141-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9141-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().