| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427664 | Information Processing Letters | 2012 | 5 Pages |
Abstract
Given a graph class GG, it is natural to ask (i) whether a given graph G has a connected or a total dominating set whose induced subgraph is a member of GG and (ii) whether G has such a set of cardinality at most a given threshold. We give sufficient conditions on GG under which these two problems are NP-hard. This condition is fulfilled in a wide variety of classes of graphs.
► Existence of connected/total dominating subgraphs of given structure is NP-hard. ► For many structures, NP-hardness remains for K1,5K1,5-free instances. ► Minimum connected/total dominating subgraph with prescribed structure is NP-hard. ► For many structures, NP-hardness remains for bip. instances with max. degree 4.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oliver Schaudt, Rainer Schrader,