Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems

摘要

Given a graph G = (V,E) on n vertices, the MAXIMUM r-REGULAR INDUCED CONNECTED SUBGRAPH (r-MaxRICS) problems ask for a maximum sized subset of vertices S (is contained in) V such that the induced subgraph G[S] on S is connected and r-regular. For r = 2, it is known that 2-MaxRICS is NP-hard and cannot be approximated within a factor of n~(1 ε) in polynomial time for any ε > 0 if P ≠ NP. In this paper, we show that r-MaxRICS is NP-hard for any fixed integer r ≥ 3, and furthermore r-MaxRICS cannot be approximated within a factor of n~(1/6) ε in polynomial time for any ε > 0 if P ≠ NP.