Inapproximability of Maximum <i>r</i>-Regular Induced Connected Subgraph Problems

DOI IR IR (HANDLE) Web Site 1 Citations 23 References Open Access
  • ASAHIRO Yuichi
    Department of Information Science, Kyushu Sangyo University
  • ETO Hiroshi
    Department of System Design and Informatics, Kyushu Institute of Technology
  • MIYANO Eiji
    Department of System Design and Informatics, Kyushu Institute of Technology

Bibliographic Information

Other Title
  • Inapproximability of maximum r-regular induced connected subgraph problems
Published
2013
Resource Type
journal article
DOI
  • 10.1587/transinf.e96.d.443
Publisher
The Institute of Electronics, Information and Communication Engineers

Search this article

Description

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.

Journal

Citations (1)*help

See more

References(23)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top