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

Broersma, Hajo and Li, Xueliang (2007) On the complexity of dominating set problems related to the minimum all-ones problem. Theoretical Computer Science, 385 (1-3). pp. 60-70. ISSN 0304-3975

PDF
Restricted to UT campus only: Request a copy
576Kb

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.
Item Type:	Article
Copyright:	© 2007 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62060
Official URL:	http://dx.doi.org/10.1016/j.tcs.2007.05.027
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 245867