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.

翻译：若一个图$G$中任意相邻顶点的度数均不相同，则称该图是\\emph{局部不规则的}。在[Fioravantes等人，《寻找最大局部不规则诱导子图的复杂性》，{\\it SWAT}, 2022]中，作者引入并研究了以下问题：对于给定图$G$，寻找其最大规模的局部不规则诱导子图，或等价地，计算$V(G)$的最小阶子集$S$，使得从$G$中删除$S$后得到的图是局部不规则的；$S$被称为$G$的\\emph{最优顶点不规则调节器}。本文深入分析了计算给定图$G$的最优顶点不规则调节器的参数化复杂度。此外，我们引入并研究了该问题的一个变体，其中$S$是$G$的边子集；此时$S$被称为$G$的\\emph{最优边不规则调节器}。具体而言，我们证明了当以图的顶点完整性、邻域多样性或聚类删除数为参数时，计算图$G$的最优顶点不规则调节器属于FPT；而当以反馈顶点集数或树深为参数时，该问题是$W[1]$-困难的。对于计算图$G$的最优边不规则调节器，我们证明当以$G$的顶点完整性为参数时，该问题属于FPT；然而即使$G$是最大度为$4$的平面二分图，该问题也是NP-困难的，并且当以解的大小、反馈顶点集数或树深为参数时，该问题是$W[1]$-困难的。我们的结果结合大多数标准图结构参数，全面描绘了本文所研究两个问题的可处理性图景。