For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
Yuichi ASAHIRO Hiroshi ETO Eiji MIYANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
induced connected subgraph, regularity, NP-hardness, inapproximability,
Full Text: PDF>>
Given a connected graph G = (V, E) on n vertices, the MAXIMUM r-REGULAR INDUCED CONNECTED SUBGRAPH (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P= NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P= NP.