IEICE TRANSACTIONS on Information
Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
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 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.443-449
- Publication Date
- 2013/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.443
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuichi ASAHIRO, Hiroshi ETO, Eiji MIYANO, "Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 3, pp. 443-449, March 2013, doi: 10.1587/transinf.E96.D.443.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.443/_p
Copy
@ARTICLE{e96-d_3_443,
author={Yuichi ASAHIRO, Hiroshi ETO, Eiji MIYANO, },
journal={IEICE TRANSACTIONS on Information},
title={Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems},
year={2013},
volume={E96-D},
number={3},
pages={443-449},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.443},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
T2 - IEICE TRANSACTIONS on Information
SP - 443
EP - 449
AU - Yuichi ASAHIRO
AU - Hiroshi ETO
AU - Eiji MIYANO
PY - 2013
DO - 10.1587/transinf.E96.D.443
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
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.
ER -
English
