Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Parameterised distan ...
Article

Parameterised distance to local irregularity

Foivos Fioravantes, Nikolaos Melissinos, Theofilos Triommatis
Download article
Open on arXiv
Submitted on
December 27, 2024
Accepted on
November 27, 2025
Published on
December 10, 2025
Last modified on
December 10, 2025
Volume 27
vol. 27:3
Graph Theory
DOI
10.46298/dmtcs.15004
License
Attribution 4.0 International (CC BY 4.0)
UK Research and Innovation
EP/S023445/1
EPSRC Centre for Doctoral Training in Distributed Algorithms: the what, how and where of next-generation data science
Indicators
417
Views
297
Downloads

Parameterised distance to local irregularity

Foivos Fioravantes, Nikolaos Melissinos, Theofilos Triommatis
Abstract
A graph $G$ is \emph{locally irregular} if no two of its adjacent vertices have the same degree. In [Fioravantes et al. Complexity of finding maximum locally irregular induced subgraph. {\it SWAT}, 2022], the authors introduced and studied the problem of finding a locally irregular induced subgraph of a given a 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 denoted as an \emph{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 substet of the edges of $G$; in this case, $S$ is denoted as an \emph{optimal edge-irregulator of $G$}. In particular, we prove that computing an optimal vertex-irregulator of a graph $G$ is in FPT when parameterised by the vertex integrity, neighborhood diversity or cluster deletion number of $G$, while it is $W[1]$-hard when parameterised by the feedback vertex set number or the treedepth of $G$. In the case of computing an optimal edge-irregulator of a graph $G$, we prove that this problem 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 $4$, 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, considering most of the standard graph-structural parameters. Final journal version
Keywords
  • Computational Complexity
  • Discrete Mathematics
  • Data Structures and Algorithms
Mathematics Subject Classification 2020
  • 05C07 - Vertex degrees
  • 05C12 - Distance in graphs
  • 05C35 - Extremal problems in graph theory
  • 05C85 - Graph algorithms (graph-theoretic aspects)
Preview
Loading PDF preview...