2023/07/10 by Fioravantes, Foivos, Melissinos, Nikolaos, Triommatis, Theofilos · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2307.04583
A graph G is 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 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 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.