TY - GEN
T1 - Complexity of finding maximum regular induced subgraphs with prescribed degree
AU - Asahiro, Yuichi
AU - Eto, Hiroshi
AU - Ito, Takehiro
AU - Miyano, Eiji
N1 - Funding Information:
The authors thank anonymous referees of the preliminary version and of this journal version for their helpful suggestions. This work is partially supported by JSPS KAKENHI Grant Numbers 23500020 and 26330017 (E. Miyano), 25106504 and 25330003 (T. Ito) and 25330018 (Y. Asahiro).
PY - 2013
Y1 - 2013
N2 - We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.
AB - We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.
UR - http://www.scopus.com/inward/record.url?scp=84883179628&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883179628&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40164-0_6
DO - 10.1007/978-3-642-40164-0_6
M3 - Conference contribution
AN - SCOPUS:84883179628
SN - 9783642401633
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 28
EP - 39
BT - Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
T2 - 19th International Symposium on Fundamentals of Computation Theory, FCT 2013
Y2 - 19 August 2013 through 21 August 2013
ER -