Parameterised distance to local irregularity

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.

This is a joint work with Foivos Fioravantes and Theofilos Triommatis.