On the complexity of dominating set problems related to the minimum allones problem
Broersma, Hajo and Li, Xueliang (2007) On the complexity of dominating set problems related to the minimum allones problem. Theoretical Computer Science, 385 (13). pp. 6070. ISSN 03043975
PDF
Restricted to UT campus only : Request a copy 590kB 
Abstract:  The minimum allones problem and the connected odd dominating set problem were shown to be NPcomplete in different papers for general graphs, while they are solvable in linear time (or trivial) for trees, unicyclic graphs, and seriesparallel 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 NPcomplete, even when restricted to bipartite graphs. We use this result to deduce that the minimum allones problem and the connected odd dominating set problem are also NPcomplete 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 NPcomplete 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 3regular graphs.

Item Type:  Article 
Copyright:  © 2007 Elsevier 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
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 
Repository Staff Only: item control page
Metis ID: 245867