TY - JOUR
T1 - Inapproximability of maximum r-regular induced connected subgraph problems
AU - Asahiro, Yuichi
AU - Eto, Hiroshi
AU - Miyano, Eiji
PY - 2013/3
Y1 - 2013/3
N2 - 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.
AB - 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.
KW - Inapproximability
KW - Induced connected subgraph
KW - NP-hardness
KW - Regularity
UR - http://www.scopus.com/inward/record.url?scp=84878238046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84878238046&partnerID=8YFLogxK
U2 - 10.1587/transinf.E96.D.443
DO - 10.1587/transinf.E96.D.443
M3 - Article
AN - SCOPUS:84878238046
SN - 0916-8532
VL - E96-D
SP - 443
EP - 449
JO - IEICE Transactions on Information and Systems
JF - IEICE Transactions on Information and Systems
IS - 3
ER -