The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article étudie les variantes généralisées du ENSEMBLE INDÉPENDANT MAXIMUM problème, appelé le DISTANCE MAXIMALE-d ENSEMBLE INDÉPENDANT problème (MaxDdEST pour faire court). Pour un entier d≥2, une distance-d ensemble indépendant d'un graphique non pondéré G=(V, E) est un sous-ensemble S⊆V de sommets tels que pour toute paire de sommets u, v∈S, le nombre d'arêtes dans n'importe quel chemin entre u et à la v Est au moins d in G. Étant donné un graphique non pondéré G, l'objectif de MaxDdIS consiste à trouver une distance de cardinalité maximale.d ensemble indépendant de G. Dans cet article, nous analysons l’(in)approximabilité du problème sur r-graphiques réguliers (r≥3) et les graphes planaires, comme suit : (1) Pour tout nombre entier fixe d≥3 et r≥3, MaxDdEst sur r-les graphiques réguliers sont APX-difficiles. (2) Nous concevons en temps polynomial O(rd-1)-approximation et O(rd-2/d)-algorithmes d'approximation pour MaxDdEst sur r-graphiques réguliers. (3) Nous affinons ce qui précède O(rd-2/d)-algorithmes d’approximation lorsqu’ils sont limités à d=r=3, et donne un algorithme de 2 approximations en temps polynomial pour MaxD3IS sur des graphes cubiques. (4) Enfin, nous montrons que MaxDdIS admet un schéma d'approximation en temps polynomial (PTAS) pour les graphes planaires.
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.
Copier
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 (MaxDdIS 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 MaxDdIS 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, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-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 MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0017/_p
Copier
@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 (MaxDdIS 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 MaxDdIS 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, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-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 MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.},
keywords={},
doi={10.1587/transfun.2021DMP0017},
ISSN={1745-1337},
month={September},}
Copier
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 (MaxDdIS 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 MaxDdIS 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, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-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 MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.
ER -