DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2024.18

Parameterised Distance to Local Irregularity

Authors: Foivos Fioravantes, Nikolaos Melissinos, and Theofilos Triommatis

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

A graph G is locally irregular if no two of its adjacent vertices have the same degree. The authors of [Fioravantes et al. Complexity of finding maximum locally irregular induced subgraph. SWAT, 2022] introduced and provided some initial algorithmic results on the problem of finding a locally irregular induced subgraph of a given graph G of maximum order, or, equivalently, computing a subset S of V(G) of minimum order, whose deletion from G results in a locally irregular graph; S is called an optimal vertex-irregulator of G. In this work we provide an in-depth analysis of the parameterised complexity of computing an optimal vertex-irregulator of a given graph G. Moreover, we introduce and study a variation of this problem, where S is a subset of the edges of G; in this case, S is denoted as an optimal edge-irregulator of G. We prove that computing an optimal vertex-irregulator of a graph G is in FPT when parameterised by various structural parameters of G, while it is W[1]-hard when parameterised by the feedback vertex set number or the treedepth of G. Moreover, computing an optimal edge-irregulator of a graph G is in FPT when parameterised by the vertex integrity of G, while it is NP-hard even if G is a planar bipartite graph of maximum degree 6, and W[1]-hard when parameterised by the size of the solution, the feedback vertex set or the treedepth of G. Our results paint a comprehensive picture of the tractability of both problems studied here.

Cite as

Foivos Fioravantes, Nikolaos Melissinos, and Theofilos Triommatis. Parameterised Distance to Local Irregularity. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fioravantes_et_al:LIPIcs.IPEC.2024.18,
  author =	{Fioravantes, Foivos and Melissinos, Nikolaos and Triommatis, Theofilos},
  title =	{{Parameterised Distance to Local Irregularity}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.18},
  URN =		{urn:nbn:de:0030-drops-222440},
  doi =		{10.4230/LIPIcs.IPEC.2024.18},
  annote =	{Keywords: Locally irregular, largest induced subgraph, FPT, W-hardness}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2022.24

Complexity of Finding Maximum Locally Irregular Induced Subgraphs

Authors: Foivos Fioravantes, Nikolaos Melissinos, and Theofilos Triommatis

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract

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) with 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 examine 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 planar bipartite, or cubic bipartite graphs. We then show that we can not even approximate an optimal solution within a ratio of 𝒪(n^{1-1/k}), where k ≥ 1 and n is the order the graph, unless 𝒫=NP, even when the input graph is bipartite. Then, looking for more positive results, we turn our attention towards computing 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Δ)^kn^{𝒪(1)}, while the second one considers the treewidth tw and Δ of G, and has running time Δ^{2tw}n^{𝒪(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 if there exists an algorithm that does not include additional parameters (other than k or tw) in its dependency. We answer negatively, to this question, by showing 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.

Cite as

Foivos Fioravantes, Nikolaos Melissinos, and Theofilos Triommatis. Complexity of Finding Maximum Locally Irregular Induced Subgraphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fioravantes_et_al:LIPIcs.SWAT.2022.24,
  author =	{Fioravantes, Foivos and Melissinos, Nikolaos and Triommatis, Theofilos},
  title =	{{Complexity of Finding Maximum Locally Irregular Induced Subgraphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.24},
  URN =		{urn:nbn:de:0030-drops-161842},
  doi =		{10.4230/LIPIcs.SWAT.2022.24},
  annote =	{Keywords: Locally irregular, largest induced subgraph, FPT, treewidth, W-hardness, approximability}
}

Search Results

Documents authored by Triommatis, Theofilos

Parameterised Distance to Local Irregularity

Abstract

Cite as

Complexity of Finding Maximum Locally Irregular Induced Subgraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message