On the complexity of dominating set problems related to the minimum all-ones problem

Hajo Broersma, Xueliang Li

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

The minimum all-ones problem and the connected odd dominating set problem were shown to be NP-complete in different papers for general graphs, while they are solvable in linear time (or trivial) for trees, unicyclic graphs, and series-parallel graphs. The complexity of both problems when restricted to bipartite graphs was raised as an open question. Here we solve both problems. For this purpose, we introduce the related decision problem of the existence of an odd dominating set without isolated vertices, and study its complexity. Our main result shows that this new problem is NP-complete, even when restricted to bipartite graphs. We use this result to deduce that the minimum all-ones problem and the connected odd dominating set problem are also NP-complete for bipartite graphs. We show that all three problems are solvable in linear time for graphs with bounded treewidth. We also show that the new problem remains NP-complete when restricted to other graph classes, e.g., planar graphs, graphs with girth at least five, and graphs with a small maximum degree, in particular 3-regular graphs.
Original languageEnglish
Pages (from-to)60-70
Number of pages11
JournalTheoretical computer science
Volume385
Issue number1-3
DOIs
Publication statusPublished - Oct 2007

Keywords

  • Planar graph
  • Odd dominating set
  • Computational Complexity
  • Bipartite graph
  • All-ones problem

Fingerprint Dive into the research topics of 'On the complexity of dominating set problems related to the minimum all-ones problem'. Together they form a unique fingerprint.

Cite this