Complexity of Finding Maximum Locally Irregular Induced Subgraphs
International audience If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular. Equivalently, given a graph...
Main Authors: | , , |
---|---|
Other Authors: | , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2022
|
Subjects: | |
Online Access: | https://hal.science/hal-03905056 https://hal.science/hal-03905056/document https://hal.science/hal-03905056/file/Largest_locally_irregular_induced_subgraph.pdf https://doi.org/10.4230/LIPIcs.SWAT.2022.23 |
id |
ftunidauphinehal:oai:HAL:hal-03905056v1 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Université Paris-Dauphine: HAL |
op_collection_id |
ftunidauphinehal |
language |
English |
topic |
FPT largest induced subgraph Locally irregular treewidth W-hardness phrases Locally irregular largest induced subgraph FPT treewidth W-hardness approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 phrases Locally irregular approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
FPT largest induced subgraph Locally irregular treewidth W-hardness phrases Locally irregular largest induced subgraph FPT treewidth W-hardness approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 phrases Locally irregular approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Fioravantes, Foivos Melissinos, Nikolaos Triommatis, Theofilos Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
topic_facet |
FPT largest induced subgraph Locally irregular treewidth W-hardness phrases Locally irregular largest induced subgraph FPT treewidth W-hardness approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 phrases Locally irregular approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular. Equivalently, given a graph G, find a subset S of V(G) of minimum order, such that by deleting the vertices of S from G results in a locally irregular graph; we denote with I(G) the order of such a set S. We first treat some easy graph families, namely paths, cycles, trees, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is NP-Complete, even for restricted families of graphs, such as subcubic bipartite, or cubic graphs. Then, looking for more positive results, we turn towards computing the parameter I(G) through the lens of parameterised complexity. In particular, we provide two algorithms that compute I(G), each one considering different parameters. The first one considers the size of the solution k and the maximum degree ∆ of G with running time (2∆)^k n^ O(1) , while the second one considers the treewidth tw and ∆ of G, and has running time ∆ ^(2tw)n^O(1). Therefore, we show that the problem is FPT by both k and tw if the graph has bounded maximum degree ∆. Since these algorithms are not FPT for graphs with unbounded maximum degree (unless we consider ∆ + k or ∆ + tw as the parameter), it is natural to wonder about the existence of an algorithm that does not include additional parameters (other than k or tw) in its dependency. We manage to settle negatively this question, and we show that our algorithms are essentially optimal. In particular, we prove that there is no algorithm that computes I(G) with dependence f (k)n^o(k) or f (tw)n^o(tw) , unless the ETH fails. |
author2 |
Combinatorics, Optimization and Algorithms for Telecommunications (COATI) Inria Sophia Antipolis - Méditerranée (CRISAM) Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA) Université Paris Dauphine-PSL Université Paris Sciences et Lettres (PSL) Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE) Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS) University of Liverpool |
format |
Conference Object |
author |
Fioravantes, Foivos Melissinos, Nikolaos Triommatis, Theofilos |
author_facet |
Fioravantes, Foivos Melissinos, Nikolaos Triommatis, Theofilos |
author_sort |
Fioravantes, Foivos |
title |
Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
title_short |
Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
title_full |
Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
title_fullStr |
Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
title_full_unstemmed |
Complexity of Finding Maximum Locally Irregular Induced Subgraphs |
title_sort |
complexity of finding maximum locally irregular induced subgraphs |
publisher |
HAL CCSD |
publishDate |
2022 |
url |
https://hal.science/hal-03905056 https://hal.science/hal-03905056/document https://hal.science/hal-03905056/file/Largest_locally_irregular_induced_subgraph.pdf https://doi.org/10.4230/LIPIcs.SWAT.2022.23 |
op_coverage |
Torshavn, Faroe Islands |
genre |
Faroe Islands Torshavn |
genre_facet |
Faroe Islands Torshavn |
op_source |
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022 https://hal.science/hal-03905056 Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022, Jun 2022, Torshavn, Faroe Islands. ⟨10.4230/LIPIcs.SWAT.2022.23⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SWAT.2022.23 hal-03905056 https://hal.science/hal-03905056 https://hal.science/hal-03905056/document https://hal.science/hal-03905056/file/Largest_locally_irregular_induced_subgraph.pdf doi:10.4230/LIPIcs.SWAT.2022.23 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.4230/LIPIcs.SWAT.2022.23 |
_version_ |
1799479639171661824 |
spelling |
ftunidauphinehal:oai:HAL:hal-03905056v1 2024-05-19T07:40:04+00:00 Complexity of Finding Maximum Locally Irregular Induced Subgraphs Fioravantes, Foivos Melissinos, Nikolaos Triommatis, Theofilos Combinatorics, Optimization and Algorithms for Telecommunications (COATI) Inria Sophia Antipolis - Méditerranée (CRISAM) Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA) Université Paris Dauphine-PSL Université Paris Sciences et Lettres (PSL) Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE) Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS) University of Liverpool Torshavn, Faroe Islands 2022-06-27 https://hal.science/hal-03905056 https://hal.science/hal-03905056/document https://hal.science/hal-03905056/file/Largest_locally_irregular_induced_subgraph.pdf https://doi.org/10.4230/LIPIcs.SWAT.2022.23 en eng HAL CCSD info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SWAT.2022.23 hal-03905056 https://hal.science/hal-03905056 https://hal.science/hal-03905056/document https://hal.science/hal-03905056/file/Largest_locally_irregular_induced_subgraph.pdf doi:10.4230/LIPIcs.SWAT.2022.23 info:eu-repo/semantics/OpenAccess Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022 https://hal.science/hal-03905056 Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022, Jun 2022, Torshavn, Faroe Islands. ⟨10.4230/LIPIcs.SWAT.2022.23⟩ FPT largest induced subgraph Locally irregular treewidth W-hardness phrases Locally irregular largest induced subgraph FPT treewidth W-hardness approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 phrases Locally irregular approximability Digital Object Identifier 10.4230/LIPIcs.SWAT.2022.23 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2022 ftunidauphinehal https://doi.org/10.4230/LIPIcs.SWAT.2022.23 2024-04-25T00:44:41Z International audience If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular. Equivalently, given a graph G, find a subset S of V(G) of minimum order, such that by deleting the vertices of S from G results in a locally irregular graph; we denote with I(G) the order of such a set S. We first treat some easy graph families, namely paths, cycles, trees, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is NP-Complete, even for restricted families of graphs, such as subcubic bipartite, or cubic graphs. Then, looking for more positive results, we turn towards computing the parameter I(G) through the lens of parameterised complexity. In particular, we provide two algorithms that compute I(G), each one considering different parameters. The first one considers the size of the solution k and the maximum degree ∆ of G with running time (2∆)^k n^ O(1) , while the second one considers the treewidth tw and ∆ of G, and has running time ∆ ^(2tw)n^O(1). Therefore, we show that the problem is FPT by both k and tw if the graph has bounded maximum degree ∆. Since these algorithms are not FPT for graphs with unbounded maximum degree (unless we consider ∆ + k or ∆ + tw as the parameter), it is natural to wonder about the existence of an algorithm that does not include additional parameters (other than k or tw) in its dependency. We manage to settle negatively this question, and we show that our algorithms are essentially optimal. In particular, we prove that there is no algorithm that computes I(G) with dependence f (k)n^o(k) or f (tw)n^o(tw) , unless the ETH fails. Conference Object Faroe Islands Torshavn Université Paris-Dauphine: HAL |