Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
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 subset of 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 n(1-epsilon) in polynomial time for any epsilon > 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 n(1/6-epsilon) in polynomial time for any epsilon > 0 unless P = NP.
inapproximability induced connected subgraph np-hardness regularity