
For FullText 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 rRegular Induced Connected Subgraph Problems
Yuichi ASAHIRO Hiroshi ETO Eiji MIYANO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.3
pp.443449 Publication Date: 2013/03/01 Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.443 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —) Category: Keyword: induced connected subgraph, regularity, NPhardness, inapproximability,
Full Text: PDF(443.6KB)>>
Summary:
Given a connected graph G = (V, E) on n vertices, the MAXIMUM rREGULAR INDUCED CONNECTED SUBGRAPH (rMaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and rregular. It is known that 2MaxRICS and 3MaxRICS are NPhard. Moreover, 2MaxRICS cannot be approximated within a factor of n^{1ε} in polynomial time for any ε > 0 unless P= NP. In this paper, we show that rMaxRICS are NPhard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, rMaxRICS cannot be approximated within a factor of n^{1/6ε} in polynomial time for any ε > 0 unless P= NP.

