The search functionality is under construction.

The search functionality is under construction.

This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-*d* INDEPENDENT SET problem (MaxD*d*IS for short). For an integer *d*≥2, a distance-*d* independent set of an unweighted graph *G*=(*V*, *E*) is a subset *S*⊆*V* of vertices such that for any pair of vertices *u*, *v*∈*S*, the number of edges in any path between *u* and *v* is at least *d* in *G*. Given an unweighted graph *G*, the goal of MaxD*d*IS is to find a maximum-cardinality distance-*d* independent set of *G*. In this paper, we analyze the (in)approximability of the problem on *r*-regular graphs (*r*≥3) and planar graphs, as follows: (1) For every fixed integers *d*≥3 and *r*≥3, MaxD*d*IS on *r*-regular graphs is APX-hard. (2) We design polynomial-time *O*(*r*^{d-1})-approximation and *O*(*r*^{d-2}/*d*)-approximation algorithms for MaxD*d*IS on *r*-regular graphs. (3) We sharpen the above *O*(*r*^{d-2}/*d*)-approximation algorithms when restricted to *d*=*r*=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxD*d*IS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1211-1222

- Publication Date
- 2022/09/01

- Publicized
- 2022/03/09

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2021DMP0017

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Algorithms and Data Structures, Graphs and Networks

Hiroshi ETO

Tohoku University

Takehiro ITO

Tohoku University

Zhilong LIU

Kyushu Insitute of Technology

Eiji MIYANO

Kyushu Insitute of Technology

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.

Copy

Hiroshi ETO, Takehiro ITO, Zhilong LIU, Eiji MIYANO, "Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1211-1222, September 2022, doi: 10.1587/transfun.2021DMP0017.

Abstract: This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-*d* INDEPENDENT SET problem (MaxD*d*IS for short). For an integer *d*≥2, a distance-*d* independent set of an unweighted graph *G*=(*V*, *E*) is a subset *S*⊆*V* of vertices such that for any pair of vertices *u*, *v*∈*S*, the number of edges in any path between *u* and *v* is at least *d* in *G*. Given an unweighted graph *G*, the goal of MaxD*d*IS is to find a maximum-cardinality distance-*d* independent set of *G*. In this paper, we analyze the (in)approximability of the problem on *r*-regular graphs (*r*≥3) and planar graphs, as follows: (1) For every fixed integers *d*≥3 and *r*≥3, MaxD*d*IS on *r*-regular graphs is APX-hard. (2) We design polynomial-time *O*(*r*^{d-1})-approximation and *O*(*r*^{d-2}/*d*)-approximation algorithms for MaxD*d*IS on *r*-regular graphs. (3) We sharpen the above *O*(*r*^{d-2}/*d*)-approximation algorithms when restricted to *d*=*r*=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxD*d*IS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0017/_p

Copy

@ARTICLE{e105-a_9_1211,

author={Hiroshi ETO, Takehiro ITO, Zhilong LIU, Eiji MIYANO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs},

year={2022},

volume={E105-A},

number={9},

pages={1211-1222},

abstract={This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-*d* INDEPENDENT SET problem (MaxD*d*IS for short). For an integer *d*≥2, a distance-*d* independent set of an unweighted graph *G*=(*V*, *E*) is a subset *S*⊆*V* of vertices such that for any pair of vertices *u*, *v*∈*S*, the number of edges in any path between *u* and *v* is at least *d* in *G*. Given an unweighted graph *G*, the goal of MaxD*d*IS is to find a maximum-cardinality distance-*d* independent set of *G*. In this paper, we analyze the (in)approximability of the problem on *r*-regular graphs (*r*≥3) and planar graphs, as follows: (1) For every fixed integers *d*≥3 and *r*≥3, MaxD*d*IS on *r*-regular graphs is APX-hard. (2) We design polynomial-time *O*(*r*^{d-1})-approximation and *O*(*r*^{d-2}/*d*)-approximation algorithms for MaxD*d*IS on *r*-regular graphs. (3) We sharpen the above *O*(*r*^{d-2}/*d*)-approximation algorithms when restricted to *d*=*r*=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxD*d*IS admits a polynomial-time approximation scheme (PTAS) for planar graphs.},

keywords={},

doi={10.1587/transfun.2021DMP0017},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1211

EP - 1222

AU - Hiroshi ETO

AU - Takehiro ITO

AU - Zhilong LIU

AU - Eiji MIYANO

PY - 2022

DO - 10.1587/transfun.2021DMP0017

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E105-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2022

AB - This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-*d* INDEPENDENT SET problem (MaxD*d*IS for short). For an integer *d*≥2, a distance-*d* independent set of an unweighted graph *G*=(*V*, *E*) is a subset *S*⊆*V* of vertices such that for any pair of vertices *u*, *v*∈*S*, the number of edges in any path between *u* and *v* is at least *d* in *G*. Given an unweighted graph *G*, the goal of MaxD*d*IS is to find a maximum-cardinality distance-*d* independent set of *G*. In this paper, we analyze the (in)approximability of the problem on *r*-regular graphs (*r*≥3) and planar graphs, as follows: (1) For every fixed integers *d*≥3 and *r*≥3, MaxD*d*IS on *r*-regular graphs is APX-hard. (2) We design polynomial-time *O*(*r*^{d-1})-approximation and *O*(*r*^{d-2}/*d*)-approximation algorithms for MaxD*d*IS on *r*-regular graphs. (3) We sharpen the above *O*(*r*^{d-2}/*d*)-approximation algorithms when restricted to *d*=*r*=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxD*d*IS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

ER -