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
Este artigo estuda variantes generalizadas do CONJUNTO INDEPENDENTE MÁXIMO problema, denominado DISTÂNCIA MÁXIMA-d CONJUNTO INDEPENDENTE problema (MaxDdÉ para abreviar). Para um número inteiro d≥2, uma distânciad conjunto independente de um gráfico não ponderado G=(V, E) é um subconjunto S⊆V de vértices tal que para qualquer par de vértices u, v∈S, o número de arestas em qualquer caminho entre u e v é pelo menos d in G. Dado um gráfico não ponderado G, o objetivo do MaxDdIS é encontrar uma distância de cardinalidade máxima-d conjunto independente de G. Neste artigo, analisamos a (in)aproximabilidade do problema em r-gráficos regulares (r≥3) e gráficos planares, como segue: (1) Para cada número inteiro fixo d≥3 e r≥3, MáxDdEstá ativado r-gráficos regulares são difíceis de APX. (2) Projetamos tempo polinomial O(rd-1)-aproximação e O(rd-2/d)-algoritmos de aproximação para MaxDdEstá ativado r-gráficos regulares. (3) Nós aprimoramos o acima O(rd-2/d)-algoritmos de aproximação quando restritos a d=r=3, e fornece um algoritmo de aproximação 2 em tempo polinomial para MaxD3IS em gráficos cúbicos. (4) Finalmente, mostramos que MaxDdIS admite um esquema de aproximação em tempo polinomial (PTAS) para grafos planares.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -