Parameterised Distance to Local Irregularity

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00378487" target="_blank" >RIV/68407700:21240/24:00378487 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.IPEC.2024.18" target="_blank" >https://doi.org/10.4230/LIPIcs.IPEC.2024.18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.IPEC.2024.18" target="_blank" >10.4230/LIPIcs.IPEC.2024.18</a>

Result language

angličtina

Original language name

Parameterised Distance to Local Irregularity

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotics and advanced industrial production</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

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

Article name in the collection

19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

ISBN

978-3-95977-353-9

ISSN

—

e-ISSN

—

Number of pages

15

Pages from-to

"18:1"-"18:15"

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl

Event location

Egham

Event date

Sep 4, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—