Parameterised distance to local irregularity

Result code in IS VaVaI

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

Result on the web

<a href="https://doi.org/10.46298/dmtcs.15004" target="_blank" >https://doi.org/10.46298/dmtcs.15004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.46298/dmtcs.15004" target="_blank" >10.46298/dmtcs.15004</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 N P-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

J_imp - Article in a specialist periodical, which is included in the Web of Science database

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

2025

Confidentiality

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

Name of the periodical

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

1365-8050

Volume of the periodical

27

Issue of the periodical within the volume

3

Country of publishing house

FR - FRANCE

Number of pages

23

Pages from-to

1-23

UT code for WoS article

001641172700002

EID of the result in the Scopus database

2-s2.0-105028262464