Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems

Yuichi ASAHIRO  Hiroshi ETO  Eiji MIYANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.443-449
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.443
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 —)
Category: 
Keyword: 
induced connected subgraph,  regularity,  NP-hardness,  inapproximability,  

Full Text: PDF(443.6KB)
>>Buy this Article


Summary: 
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 SV 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.