TY - JOUR

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).
Publisher Copyright:
© 2014 Elsevier B.V.

PY - 2014

Y1 - 2014

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=84926407099&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84926407099&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.07.008

DO - 10.1016/j.tcs.2014.07.008

M3 - Article

AN - SCOPUS:84926407099

SN - 0304-3975

VL - 550

SP - 21

EP - 35

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -