Maximum locally irregular induced subgraphs via minimum irregulators

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00385534" target="_blank" >RIV/68407700:21240/25:00385534 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.dam.2024.12.007" target="_blank" >https://doi.org/10.1016/j.dam.2024.12.007</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2024.12.007" target="_blank" >10.1016/j.dam.2024.12.007</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Maximum locally irregular induced subgraphs via minimum irregulators

Popis výsledku v původním jazyce

If a graph G is such that no two of its adjacent vertices have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of finding a largest locally irregular induced subgraph of a given graph G. Equivalently, given a graph G, find a subset S of V(G) with minimum order, such that 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, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is N P-Complete, even for restricted families of graphs, such as subcubic planar bipartite, or cubic bipartite graphs. We then show that we cannot even approximate an optimal solution within a ratio of O(n1- 1k), where k >= 1 and n is the order of the graph, unless P=N P, 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 triangle of G with running time (2 triangle)knO(1), while the second one considers the treewidth tw and triangle of G, and has running time triangle 3twnO(1). Therefore, we show that the problem is in FPT by both k and tw if the graph has bounded maximum degree triangle. Since the algorithms we present are not in FPT for graphs with unbounded maximum degree (unless we consider triangle + k or triangle + 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. In particular, we prove that there is no algorithm that computes I(G) with dependence f (k)no(k) or f (tw)no(tw), unless the ETH fails, showing that our algorithms are essentially optimal. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Název v anglickém jazyce

Maximum locally irregular induced subgraphs via minimum irregulators

Popis výsledku anglicky

If a graph G is such that no two of its adjacent vertices have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of finding a largest locally irregular induced subgraph of a given graph G. Equivalently, given a graph G, find a subset S of V(G) with minimum order, such that 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, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is N P-Complete, even for restricted families of graphs, such as subcubic planar bipartite, or cubic bipartite graphs. We then show that we cannot even approximate an optimal solution within a ratio of O(n1- 1k), where k >= 1 and n is the order of the graph, unless P=N P, 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 triangle of G with running time (2 triangle)knO(1), while the second one considers the treewidth tw and triangle of G, and has running time triangle 3twnO(1). Therefore, we show that the problem is in FPT by both k and tw if the graph has bounded maximum degree triangle. Since the algorithms we present are not in FPT for graphs with unbounded maximum degree (unless we consider triangle + k or triangle + 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. In particular, we prove that there is no algorithm that computes I(G) with dependence f (k)no(k) or f (tw)no(tw), unless the ETH fails, showing that our algorithms are essentially optimal. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

O - Projekt operacniho programu

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

363

Číslo periodika v rámci svazku

March

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

168-189

Kód UT WoS článku

001389579700001

EID výsledku v databázi Scopus

2-s2.0-85211590335