# Parameterised distance to local irregularity ††thanks: The third author is
supported by EP/S023445/1 EPSRC CDT in Distributed Algorithms, University of
Liverpool.

Foivos Fioravantes  Department of Theoretical Computer Science, Faculty of
Information Technology, Czech Technical University in Prague, Prague, Czech
Republic Nikolaos Melissinos  Department of Theoretical Computer Science,
Faculty of Information Technology, Czech Technical University in Prague,
Prague, Czech Republic Theofilos Triommatis  School of Electrical Engineering,
Electronics and Computer Science
University of Liverpool, Liverpool, L69-3BX, UK

###### Abstract

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. 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 ${\rm 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 $\mathcal{NP}$-hard even if $G$ is a planar bipartite graph of
maximum degree $4$, and ${\rm 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.

  * Keywords:

Locally irregular, largest induced subgraph, FPT, W-hardness

##  1 Introduction

A fundamental problem in graph theory is “given a graph $G$, find an induced
subgraph $H$ of $G$, of maximum order, that belongs in the family of graphs
verifying a property $\Pi$”, in which case we say that $H\in\Pi$:

Input: A graph $G=(V,E)$, an integer $k$, a property $\Pi$. Question: Does
there exist a set $S\subseteq V$ such that $|S|\leq k$ and $G-S\in\Pi$?
Largest Induced Subgraph with Property $\Pi$ (ISP$\Pi$)[18]

There is a plethora of classical problems that fall under this general
setting. Consider for example the Vertex Cover and the Feedback Vertex Set,
where $\Pi$ is the property “the graph is an independent set” and “the graph
is a forest”, respectively.

In this paper we study the ISP$\Pi$ problem where $\Pi$ is the property “the
graph is locally irregular”, recently introduced in [15]. A graph $G=(V,E)$ is
called _locally irregular_ if no two adjacent vertices in $V$ have the same
degree. We extend the work presented in [15], by more thoroughly investigating
the behaviour of the problem in regards to parameterised complexity. In
addition, we take the first step towards the problem of finding large locally
irregular (not necessarily induced) subgraphs of a given graph $G$. In
particular, we introduce the problem where the goal is to find a subset of
edges of $G$ of maximum order, whose removal renders the graph locally
irregular. Our results allow us to paint a rather clear picture concerning the
tractability of both problems studied here, considering many standard graph-
structural parameters (see Figure 1 for an overview of our results).

Figure 1: Overview of our results. A parameter $A$ appearing linked to a
parameter $B$ with $A$ being below $B$ is to be understood as “$A$ is at least
as large as $B$”. In light blue and olive we exhibit the FPT results we
provide for the problems of finding an optimal vertex and edge (respectively)
irregulator. In red we exhibit the ${\rm W}[1]$-hardness results we provide
for both problems.

ISP$\boldsymbol{\Pi}$ and hereditarity. The ISP$\Pi$ problem has been
extensively studied in the case where $\Pi$ is a _hereditary_ property.
Formally, a property $\Pi$ is _hereditary_ if, for any graph $G$ verifying
that property, it holds that any induced subgraph of $G$ also verifies that
property (notice that the properties mentioned previously are indeed
hereditary). It was already shown in [27] that ISP$\Pi$ is a hard problem for
any non-trivial hereditary property. On the positive side, the ISP$\Pi$
problem always admits an FPT algorithm, when parameterised by the size of the
solution, if $\Pi$ is a hereditary property [8, 23]. This is an important
result, as it allows us to conceive efficient algorithms to solve
computationally hard problems, as long as we restrict ourselves to graphs
verifying such properties.

It is also worth mentioning the work in [16], which provides a framework that
yields exact algorithms that are significantly faster than brute-force to
solve a more general version of the ISP$\Pi$ problem: given a universe, find a
subset of maximum cardinality which verifies some hereditary property. On a
high level, the algorithm proposed in [16] builds the solution which is a
subset $H$ of maximum cardinality with the wanted property, by continuously
extending a partial solution $X\subseteq H$. Note that this approach only
works if $\Pi$ is indeed a hereditary property. More recently, this approach
was generalised by the authors of [13], who provide a framework that yields
exponential-time approximation algorithms.

However, not all interesting properties are hereditary. E.g., “all vertices of
the induced subgraph have odd degree”, and “the induced subgraph is
$d$-regular”, where $d$ is an integer given in the input (recall that a graph
is $d$-_regular_ if all of its vertices have the same degree $d$), are two
non-hereditary properties. The authors of [5] studied the ISP$\Pi$ problem for
the former property, showing that this is an $\mathcal{NP}$-hard problem, and
providing an FPT algorithm that solves the problem when parameterised by the
rank-width. Also, the authors of [1, 3, 28] studied the ISP$\Pi$ problem for
the latter property. In particular, in [3] it is shown that finding a
(connected) induced subgraph of maximum order that is $d$-regular, is
$\mathcal{NP}$-hard to approximate, even when restricted on bipartite or
planar graphs. The authors of [3] also provide a linear-time algorithm to
solve this problem for graphs with bounded treewidth. Lastly, it is also worth
mentioning [7], where the authors consider the non-hereditary property “the
induced subgraph is $k$-anonymous”, where a graph $G$ is $k$-anonymous if for
each vertex of $G$ there are at least $k-1$ other vertices of the same degree.

An important observation is that, in the case of non-hereditary properties,
the ISP$\Pi$ problem does not necessarily admit an FPT algorithm parameterised
by the size of the solution. Indeed, the authors of [28] proved that when
considering $\Pi$ as “the induced subgraph is regular”, the ISP$\Pi$ problem
is ${\rm W}[1]$-hard when parameterised by the size of the solution. This
indicates the importance of considering graph-structural parameters for
conceiving efficient algorithms for such problems. This is exactly the
approach followed in [17, 25], where the authors consider a generalisation of
Vertex Cover, the ISP$\Pi$ problem where $\Pi$ is “the graph has maximum
degree $k$”, for an integer $k$ given in the input.

Distance from local irregularity. In some sense, the property that interests
us lies on the opposite side of the one studied in [1, 3, 28]. Recall that a
graph $G$ is locally irregular if no two of its adjacent vertices have the
same degrees. The notion of locally irregular graphs was formally introduced
in [4], where the authors take some steps towards proving the so-called 1-2-3
Conjecture proposed in [21] and claimed to be solved recently in [22].
Roughly, this conjecture is about functions assigning weights from
$[k]=\\{1,\dots,k\\}$ to the edges of a graph, called proper $k$-labellings,
so that all adjacent vertices have different weighted degrees; the conjecture
states that for any non-trivial graph, this should always be achievable for
$k\leq 3$.

In [15], the authors introduced and studied the problem of finding a locally
irregular induced subgraph of a given graph $G$ of maximum order (a non-
hereditary property). Equivalently, given a graph, find a set of _vertices_ of
minimum cardinality, whose deletion renders the graph locally irregular; such
sets are named _optimal vertex-irregulators_. The main focus of [15] was to
study the complexity of computing an optimal vertex-irregulator of a given
graph. Among other results, it was shown that this problem is
$\mathcal{NP}$-hard even for subcubic planar bipartite graphs, ${\rm
W}[2]$-hard parameterised by the size of the solution and ${\rm W}[1]$-hard
parameterised by the treewidth of the input graph. Moreover, for any constant
$\varepsilon<1$, there cannot be a polynomial-time
$\mathcal{O}(n^{1-\varepsilon})$-approximation algorithm. On the positive
side, there are two FPT algorithms that solve this problem, parameterised by
the maximum degree of the input graph plus either the size of the solution or
the treewidth of the input graph. Note that the notion of vertex-irregulators
proved to be fruitful in the context of proper labellings. Indeed, the authors
of [6] observed a connection between finding large locally irregular induced
subgraphs and constructing proper $k$-labellings that also maximise the use of
weight $1$ on the edges of the given graph.

Apart from improving the results of [15], in this paper we also introduce the
novel problem of computing a subset of a graph’s _edges_ , of minimum order,
whose deletion renders the graph locally irregular; such sets are named
_optimal edge-irregulators_. This problem is introduced as a first step
towards understanding the problem of finding large locally irregular (not
necessarily induced) subgraphs of a given graph. Problems concerned with
finding maximum subgraphs verifying a specific property have also been
extensively studied (_e.g._ , [9, 10, 2]). One might expect that finding edge-
irregulators could be easier than finding vertex-irregulators as it is often
the case with graph theoretical problems concerned with subsets of edges,
whose versions considering subsets of vertices are intractable (recall, _e.g._
, the Edge Cover, the Feedback Edge Set and even the Min Weighted Lower-Upper-
Cover [29]). As it turns out, however, finding large edge-irregulators is also
a computationally hard problem.

Our contribution. In this paper we study the complexity of computing optimal
vertex and edge-irregulators. Our results allow us to identify the parameters
for which the tractability of the former problem changes, considering almost
all standard graph-structural parameters. We also take steps towards the same
goal for the latter problem. In Section 2 we introduce the needed notation and
provide some first results. In particular, we observe that computing optimal
vertex-irregulators is ${\rm W}[1]$-hard when parameterised by the treedepth
or the feedback vertex set of the given graph. Section 3 is focused on
providing FPT algorithms for the problem of finding optimal vertex-
irregulators, parameterised by the neighborhood diversity or the vertex
integrity of the input graph. In Section 4, we focus on the problem of finding
optimal edge-irregulators. First, we prove that this problem is
$\mathcal{NP}$-hard, even when restricted to planar bipartite graphs of
maximum degree $4$. We also show that the problem is ${\rm W}[1]$-hard
parameterised by the size of the solution or the feedback vertex set of the
input graph. Lastly, we modify the FPT algorithm for computing an optimal
vertex-irregulator parameterised by the vertex integrity in order to provide
an FPT algorithm that solves the edge version of the problem (once more
parameterised by the vertex integrity). We close the paper in Section 5, where
we propose some directions for further research.

##  2 Preliminaries

For notions and definitions of graph theory not explained here, we refer the
reader to [11].

Let $G=(V,E)$ be a graph and $G^{\prime}=(V^{\prime},E^{\prime})$ be a
subgraph of $G$ (i.e., created by deleting vertices and/or edges of $G$).
Recall first that the subgraph $G^{\prime}$ is _induced_ if it can be created
only by deleting vertices of $G$. That is, for each edge $uv\in E$, if $u,v\in
V^{\prime}$, then $uv\in E^{\prime}$. For any vertex $v\in V$, let
$N_{G}(v)=\\{u\in V:uv\in E\\}$ denote the _neighbourhood_ of $v$ in $G$ and
$d_{G}(v)=|N_{G}(v)|$ denote the _degree_ of $v$ in $G$. Note that, whenever
the graph $G$ is clear from the context, we will omit the subscript and simply
write $N(v)$ and $d(v)$. Also, for $S\subseteq E$, denote by $G-S$ the graph
$G^{\prime}=(V,E\setminus S)$. That is, $G^{\prime}$ is the graph resulting
from the deletion of the edges of $S$ from the graph $G$.

Let $G=(V,E)$ be a graph. We say that $G$ is _locally irregular_ if, for every
edge $uv\in E$, we have $d(u)\neq d(v)$. Now, let $S\subseteq V$ be such that
$G[V\setminus S]$ is a locally irregular graph; any set $S$ that has this
property is denoted as a _vertex-irregulator of $G$_. Moreover, let ${\rm
I}_{v}(G)$ be the minimum order that any vertex-irregulator of $G$ can have.
We will say that $S$ is an _optimal_ vertex-irregulator of $G$ if $S$ is a
vertex-irregulator of $G$ and $|S|={\rm I}_{v}(G)$. Similarly, we define an
_edge-irregulator of $G$_ to be any set $S\subseteq E$ such that $G-S$ is
locally irregular. Moreover, let ${\rm I}_{e}(G)$ be the minimum order that
any edge-irregulator of $G$ can have. We will say that $S$ is an _optimal_
edge-irregulator of $G$ if $S$ is an edge-irregulator of $G$ and $|S|={\rm
I}_{e}(G)$.

The next simple observation is quite useful when proving lower bounds on an
optimal vertex or edge-irregulator of a graph.

######  Observation 2.1.

Let $G=(V,E)$ be a graph containing two vertices $u,v$ such that $uv\in E$ and
$d(u)=d(v)$. Any edge-irregulator of $G$ contains at least one edge incident
to $u$ or $v$. Also, any vertex-irregulator of $G$ contains at least one
vertex in $N(u)\cap N(v)$.

Let $G=(V,E)$ be a graph. We say that two vertices $u$, $v$ of $V$ are _twins_
if $N(u)\setminus\\{v\\}=N(v)\setminus\\{u\\}$, i.e., they have the same
neighbourhoods.

######  Observation 2.2.

Let $G=(V,E)$ be a graph and $u,v\in V$ be a set of twins of $G$ such that
$uv\in E$. Any vertex-irregulator of $G$ contains at least one vertex in
$\\{u,v\\}$.

Indeed, by Observation 2.1, we get that any vertex-irregulator $S$ of $G$
includes at least one neighbour of $u$ or $v$. If we assume that
$S\cap\\{u,v\\}=\emptyset$, then $u$ and $v$ are once more adjacent twins in
$G[V\setminus S]$, contradicting the fact that $S$ is a vertex-irregulator.

The importance of the upcoming Lemma 2.3 lies in the fact that we can
repeatedly apply it and reduce the size of the graph on which we are searching
for a vertex-irregulator, as long as the reduced graph contains a pair of
adjacent twins. This is a core argument behind the algorithms presented in
Theorems 3.2 and 3.6.

######  Lemma 2.3.

Let $G=(V,E)$ be a graph and $u,v\in V$ be a pair of adjacent twins. Let
$G^{\prime}=(V^{\prime},E^{\prime})$ be the graph resulting from the deletion
of either $u$ or $v$ from $G$. Then, ${\rm I}_{v}(G)={\rm
I}_{v}(G^{\prime})+1$.

###### Proof.

Assume w.l.o.g. that $u\notin V^{\prime}$. We first prove that ${\rm
I}_{v}(G)\leq{\rm I}_{v}(G^{\prime})+1$. Indeed, assume that ${\rm
I}_{v}(G)>{\rm I}_{v}(G^{\prime})+1$ and let $S^{\prime}$ be an optimal
vertex-irregulator of $G^{\prime}$. Next, consider the graph
$\tilde{G}=G[V\setminus(S^{\prime}\cup\\{u\\})]$. From the construction of
$G^{\prime}$, it follows that $\tilde{G}=G^{\prime}[V^{\prime}\setminus
S^{\prime}]$. Since $S^{\prime}$ is a vertex-irregulator of $G^{\prime}$, we
obtain that $\tilde{G}$ is locally irregular. In other words, the set
$S^{\prime}\cup\\{u\\}$ is a vertex-irregulator of $G$ and
$|S^{\prime}\cup\\{u\\}|=I_{v}(G^{\prime})+1$, a contradiction.

Next, assume that ${\rm I}_{v}(G)<{\rm I}_{v}(G^{\prime})+1$ and let $S$ be an
optimal vertex-irregulator of $G$. It follows from Observation 2.2 that
$|\\{u,v\\}\cap S|\geq 1$. Assume w.l.o.g. that $u\in S$. Thus, and by the
construction of $G^{\prime}$, we have that
$G^{\prime}[V^{\prime}\setminus(S\setminus\\{u\\})]=G[V\setminus S]$ and the
set $S\setminus\\{u\\}$ is a vertex-irregulator of $G^{\prime}$. In other
words, ${\rm I}_{v}(G^{\prime})\leq|S|-1={\rm I}_{v}(G)-1$, a contradiction. ∎

We close this section with some observations on the proof that computing ${\rm
I}_{v}(G)$ is ${\rm W}[1]$-hard parameterised by the treewidth of $G$,
initially presented in [15], which allow us to show that this result holds
even if we consider more “generous” parameters, such as the treedepth or the
the feedback vertex set number (_i.e._ , size of a minimum feedback vertex
set) of the input graph. Recall that the _treedepth_ of a graph $G=(V,E)$ can
be defined recursively: if $|V|=1$ then $G$ has treedepth $1$. Then, $G$ has
treedepth $k$ if there exists a vertex $v\in V$ such that every connected
component of $G[V\setminus\\{v\\}]$ has treedepth at most $k-1$. Given a graph
$G$ and a tree $T$ rooted at a vertex $u$, by _attaching_ $T$ on a vertex $v$
of $G$ we mean the operation of adding $T$ to $G$ and identifying $u$ with
$v$.

######  Observation 2.4.

Let $G$ be a graph with vertex cover number (_i.e._ , size of a minimum vertex
cover) $k_{1}$ and $T$ be a rooted tree of depth $k_{2}$. Let $G^{\prime}$ be
the graph resulting from attaching an arbitrary number of copies of $T$
directly on vertices of $G$. Then $G^{\prime}$ has treedepth
$\mathcal{O}(k_{1}+k_{2})$ and feedback vertex set number
$\mathcal{O}(k_{1})$.

The reduction presented in [15, Theorem $16$] starts with a graph $G$ which is
part of an instance of the List Colouring problem, and constructs a graph
$G^{\prime}$ by attaching some trees of depth at most $3$ on each vertex of
$G$. The List Colouring problem was shown to be ${\rm W}[1]$-hard in [14] when
parameterised by the vertex cover number of the input graph. Thus, and by
Observation 2.4, we obtain the following:

######  Corollary 2.5.

Given a graph $G$, it is ${\rm W}[1]$-hard to compute ${\rm I}_{v}(G)$
parameterised by either the treedepth or the feedback vertex set number of
$G$.

##  3 FPT algorithms for vertex-irregulators

In this section we present two FPT algorithms that compute an optimal vertex-
irregulator of a given graph $G$, when parameterised by the neighbourhood
diversity or the vertex integrity of $G$. The latter algorithm is then used to
show that this problem is in FPT also when parameterised by the cluster
deletion number of $G$. We begin by recalling the needed definitions.

The _twin equivalence_ of $G$ is the relation on the vertices of $V$ according
to which two vertices belong to the same equivalence class if and only if they
are twins.

######  Definition 3.1 ([24]).

The _neighbourhood diversity_ of a graph $G$, denoted by $nd(G)$, is the
number $k$ of classes of the twin equivalence of $G$.

Let $G=(V,E)$ be a graph with $nd(G)=k$ and let $V_{1},\dots,V_{k}$ be the
partition of $V$ defined by the twin equivalence of $G$. Observe that for any
$i\in[k]$, we have that $G[V_{i}]$ is either an independent set or a clique.

######  Theorem 3.2.

Given a graph $G=(V,E)$ such that $nd(G)=k$, there exists an algorithm that
computes ${\rm I}_{v}(G)$ in FPT-time parameterised by $k$.

###### Proof.

Let $V_{1},\dots,V_{k}$ be the partition of $V$ defined by the twin
equivalence of $G$. Recall that for any $i\in[k]$, we have that $G[V_{i}]$ is
either an independent set or a clique. We begin by constructing an induced
subgraph $G^{\prime}=(V^{\prime},E^{\prime})$ of $G$ by applying the following
procedure: for each $i\in[k]$, if $G[V_{i}]$ is a clique on at least two
vertices, then delete all the vertices of $V_{i}$ except one; let $D$ be the
set of vertices that were deleted in this fashion throughout the procedure and
$d=|D|$. Observe that this procedure terminates after $k$ repetitions and,
thus, runs in polynomial time (in regards to $|V|$). Moreover, it follows from
Lemma 2.3 that ${\rm I}_{v}(G)={\rm I}_{v}(G^{\prime})+d$. Thus, in order to
compute ${\rm I}_{v}(G)$, it suffices to compute ${\rm I}_{v}(G^{\prime})$. To
achieve that, we model this problem as an ILP on a bounded number of
variables. For every $i\in[k]$, let $V^{\prime}_{i}=V_{i}\cap V^{\prime}$.
Also, for every $i\in[k]$, let $N(i)=\\{j\in[k]\mid\exists u\in
V^{\prime}_{j}\text{ and }v\in V^{\prime}_{i}\text{ s.t. }uv\in
E^{\prime}\\}$. That is, $N(i)$ is the set of indices of the neighbouring
partitions of vertices in $V^{\prime}_{i}$. Finally, we guess a partition of
$[k]$ into $S_{1}$ and $S_{2}$ (there are at most $2^{k}$ such partitions),
such that, if $S^{\prime}$ is a vertex-irregulator of $G^{\prime}$, then
$S^{\prime}\cap V^{\prime}_{i}=V^{\prime}_{i}$ for all $i\in S_{2}$, and
$S^{\prime}\cap V^{\prime}_{i}\neq V^{\prime}_{i}$ for all $i\in S_{1}$.

Variables

$x_{i}\in[|V^{\prime}_{i}|]$ | $i\in S_{1}$ |  number of vertices remaining in a subset of $V^{\prime}_{i}$
---|---|---

Objective

$\displaystyle\max\sum_{i=1}^{k}x_{i}$ (3.1)

Constraints

$\displaystyle\sum_{\ell\in N(i)}x_{\ell}\neq\sum_{\ell\in N(j)}x_{\ell}$
$\displaystyle\forall i,j\in S_{1}\text{ s.t. }j\in N(i)$ (3.2)

The variable $x_{i}$ is used in the above model to represent the vertices that
will remain in $V^{\prime}_{i}$, for each $i\in S_{1}$, after the deletion of
an optimal vertex-irregulator $S^{\prime}$ of $G^{\prime}$. The constraint 3.2
makes sure that any two adjacent vertices $u,v\in V^{\prime}$ have different
degrees in $G^{\prime}[V^{\prime}\setminus S^{\prime}]$. Indeed, for each
$uv\in E^{\prime}$, there exist $i,j$ such that $u\in V^{\prime}_{i}$ and
$v\in V^{\prime}_{j}$. If either $i\in S_{2}$ or $j\in S_{2}$ (or both), then
$u\in S^{\prime}$ or $v\in S^{\prime}$ (or both). Thus, we can assume that
$i,j\in S_{1}$. In this case, it follows from the constraint 3.2 that
$d_{G^{\prime}[V^{\prime}\setminus S^{\prime}]}(u)=\sum_{\ell\in
N(i)}x_{\ell}\neq\sum_{\ell\in N(j)}x_{\ell}=d_{G^{\prime}[V\setminus
S^{\prime}]}(v)$. In any case, $G^{\prime}[V^{\prime}\setminus S^{\prime}]$ is
locally irregular. Finally, since the model has $k$ variables, we can and
obtain $S^{\prime}$ in FPT time, parameterised by $k$ (by running for example
the Lenstra algorithm [26]). ∎

We now present an FPT algorithm to compute an optimal vertex-irregulator of an
input graph $G$ when parameterised by the vertex integrity of $G$.

######  Definition 3.3.

A graph $G=(V,E)$ has _vertex integrity_ $k$ if there exists a set $U\subseteq
V$ such that $|U|=k^{\prime}\leq k$ and all connected components of
$G[V\setminus U]$ are of order at mots $k-k^{\prime}$.

It is known that we can find such a set in FPT-time parameterised by $k$ [12].

######  Theorem 3.4.

Given a graph $G=(V,E)$ with vertex integrity $k$, there exists an algorithm
that computes ${\rm I}_{v}(G)$ in FPT-time parameterised by $k$.

###### Proof.

Let $U$ be such that $|U|=k^{\prime}\leq k$ and $C_{1},\ldots,C_{m}$ be the
vertex sets of the connected components of $G[V\setminus U]$. It follows that
$|C_{j}|\leq k$, $j\in[m]$. Assume that we know the intersection of an optimal
vertex-irregulator $S$ of $G$ and the set $U$, and let $S^{\prime}=S\cap U$
and $U^{\prime}=U\setminus S$ (there are at most $2^{|U|}\leq 2^{k}$ possible
intersections $S^{\prime}$ of $U$ and $S$.). Notice that the graph
$G[V\setminus S^{\prime}]$ has an optimal vertex-irregulator that contains
only vertices from $\bigcup_{i\in[m]}C_{i}$. Indeed, assuming otherwise
contradicts that $S^{\prime}$ is the intersection of an optimal vertex-
irregulator and $U$. Thus, in order to find an optimal vertex-irregulator $S$
of $G$, it suffices to compute $S^{*}\subseteq\bigcup_{i\in[m]}C_{i}$, which
is an optimal vertex-irregulator of $G[V\setminus S^{\prime}]$, for every set
$S^{\prime}\subseteq U$. Then, we return the set $S^{*}\cup S^{\prime}$ of
minimum order. We compute $S^{*}$ through an ILP with bounded number of
variables. To do so, we define types and sub-types of graphs $G[U^{\prime}\cup
C_{j}]$.

Informally, the main idea is to categorise the graphs $G[U^{\prime}\cup
C_{j}]$, $j\in[m]$, into types based on their structure (formally defined
later), whose number is bounded by $k$. Each type $i$ is associated to a
number $no_{i}$ that represents the number of the subgraphs $G[U^{\prime}\cup
C_{j}]$, $j\in[m]$, that belong in that type. Then, for each type $i$, we will
define sub-types based on the induced subgraphs $G[(U^{\prime}\cup
C_{j})\setminus S_{q}]$, for $S_{q}\subseteq C_{j}$. We also define a variable
$no_{i,q}$ that is the number of the subgraphs $G[U^{\prime}\cup C_{j}]$,
$j\in[m]$, that are of type $i$ and of sub-type $q$ in $G[V\setminus S]$. Note
that knowing the structure of these types and sub-types, together with
$no_{i,q}$, is enough to compute the order of $S^{*}$. Finally, for any
$j\in[m]$, the graph $G[U^{\prime}\cup C_{j}]$ is of order at most $k$. Thus,
the number of types, sub-types and their corresponding variables, is bounded
by a function of $k$. We will present an ILP formulation whose objective is to
minimise the order of $S^{*}$.

We begin by defining the types. Two graphs $G[U^{\prime}\cup C_{i}]$ and
$G[U^{\prime}\cup C_{j}]$, $i,j\in[m]$, are of the same type if there exists a
bijection111Recall that a function $f:A\rightarrow B$ is a _bijection_ if, for
every $a_{1},a_{2}\in A$ with $a_{1}\neq a_{2}$, we have that $f(a_{1})\neq
f(a_{2})$ and for every $b\in B$, there exists an $a\in A$ such that $f(a)=b$.
Recall also that the _inverse_ function of $f$, denoted as $f^{-1}$, exists if
and only if $f$ is a bijection, and is such that $f^{-1}:B\rightarrow A$ and
for each $b\in B$ we have that $f^{-1}(b)=a$, where $f(a)=b$. $f:C_{i}\cup
U^{\prime}\rightarrow C_{j}\cup U^{\prime}$ such that $f(u)=u$ for all $u\in
U^{\prime}$ and $N_{G[U^{\prime}\cup C_{i}]}(u)=\\{f^{-1}(v)\mid v\in
N_{G[U^{\prime}\cup C_{j}]}(f(u))\\}$ for all $u\in C_{i}$. Note that if such
a function exists, then $G[U^{\prime}\cup C_{i}]$ is isomorphic to
$G[U^{\prime}\cup C_{j}]$.

Let $p$ be the number of different types. Notice that $p$ is bounded by a
function of $k$ as any graph $G[U^{\prime}\cup C_{i}]$ has order at most $k$.
Also, we can decide if two graphs $G[U^{\prime}\cup C_{i}]$ and
$G[U^{\prime}\cup C_{j}]$, $i,j\in[m]$, are of the same type in FPT-time
parameterised by $k$. For each type $i\in[p]$, set $no_{i}$ to be the number
of graphs $G[U^{\prime}\cup C_{j}]$, $j\in[m]$, of type $i$. Furthermore, for
each type $i\in[p]$ we select a $C_{j}$, $j\in[m]$, such that
$G[U^{\prime}\cup C_{j}]$ is of type $i$, to represent that type; we will
denote this set of vertices by $C^{\prime}_{i}$.

We are now ready to define the sub-types. Let $i\in[p]$ be a type represented
by $C^{\prime}_{i}$ and $S^{i}_{1}\ldots,S^{i}_{2^{|C^{\prime}_{i}|}}$be an
enumeration of the subsets of $C^{\prime}_{i}$. For any
$q\in[2^{|C^{\prime}_{i}|}]$ we define a sub-type $(i,q)$ which represents the
induced subgraph $G[(U^{\prime}\cup C^{\prime}_{i})\setminus S_{q}]$. Set
$no_{i,q}$ to be the number of graphs represented by $G[U^{\prime}\cup
C^{\prime}_{i}]$, $i\in[p]$, that are of type $(i,q)$ in $G[V\setminus
S^{*}]$, for a vertex-irregulator $S^{*}$ ,_i.e._ , $S^{*}\cap
C^{\prime}_{i}=S^{i}_{q}$.

Notice that, given a vertex-irregulator $S^{*}\subseteq\bigcup_{j\in[m]}C_{j}$
of $G[V\setminus S^{\prime}]$, there exists a sub-type $(i,q)$, $i\in[p]$,
$q\in[2^{|C^{\prime}_{i}|}]$, such that the graph $G[(U^{\prime}\cup
C_{j})\setminus S^{*}]$ is of sub-type $(i,q)$, for all $j\in[m]$. Also,
assuming that we know the order of $|S^{i}_{q}|$ and the number $no_{i,q}$ for
all $i\in[p]$, $q\in[2^{|C^{\prime}_{i}|}]$, then
$|S^{*}|=\sum_{i\in[p]}\sum_{q\in[2^{|C^{\prime}_{i}|}]}no_{i,q}|S^{i}_{q}|$.

Before giving the ILP formulation whose goal is to find a vertex-irregulator
$S^{*}$ while minimising the above sum, we guess the $(i,q)$ such that
$no_{i,q}\neq 0$. Let $S_{2}$ be the set of pairs $(i,q)$ $i\in[p]$ and
$q\in[2^{|C^{\prime}_{i}|}]$, such that there are two vertices $u,v\in
C^{\prime}_{i}\setminus S^{i}_{q}$ where $uv\in E(G[(U^{\prime}\cup
C_{i})\setminus S^{i}_{q}])$ and $d_{G[(U^{\prime}\cup
C^{\prime}_{i})\setminus S^{i}_{q}]}(u)=d_{G[(U^{\prime}\cup
C^{\prime}_{i})\setminus S^{i}_{q}]}(v)$. For every $(i,q)\in S_{2}$, we have
that $no_{i,q}=0$. Indeed, assuming otherwise contradicts the fact that
$S^{*}$ is a vertex-irregulator. We guess $S_{1}\subseteq\\{(i,q)\mid
i\in[p],q\in 2^{|C^{\prime}_{i}|}\\}\setminus S_{2}$ such that $no_{i,q}\neq
0$ for all $(i,q)\in S_{1}$. Observe that the number of different sets that
are candidates for $S_{1}$ are at most some function of $k$.

Constants

$no_{i}$ | $i\in[p]$ |  number of components of type $i$
---|---|---
$e_{uv}\in\\{0,1\\}$ | $u,v\in U^{\prime}$ |  set to $1$ iff $uv\in E(G[U^{\prime}])$
$e^{i,q}_{u,v}\in\\{0,1\\}$ |  $i\in[p],q\in[2^{|C^{\prime}_{i}|}]$, $u\in U^{\prime}$ |  set to $1$ iff $uv\in E(G[(U^{\prime}\cup C^{\prime}_{i})\setminus S^{i}_{q}])$
|  and $v\in C^{\prime}_{i}\setminus S^{i}_{q}$ |
$b^{i,q}_{u}\in[n]$ |  $i\in[p],q\in[2^{|C^{\prime}_{i}|}]$ and $u\in U^{\prime}$ |  set to $d_{G[(U^{\prime}\cup C^{\prime}_{i})\setminus S^{i}_{q}]}(u)$
$d^{i,q}_{u}\in[n]$ |  $i\in[p],q\in[2^{|C^{\prime}_{i}|}]$ and $u\in C^{\prime}_{i}\setminus S^{i}_{q}$ |  set to $d_{G[(U^{\prime}\cup C^{\prime}_{i})\setminus S^{i}_{q}]}(u)$

Variables

$no_{i,q}$ | $i\in[p],q\in[2^{|C^{\prime}_{i}|}]$ |  number of types $(i,q)$
---|---|---

Objective

$\displaystyle\min\sum_{i\in[p]}no_{i,q}|S^{i}_{q}|$ (3.3)

Constraints

$\displaystyle no_{i,q}=0$ $\displaystyle\text{ iff }(i,q)\notin S_{1}$ (3.4)
$\displaystyle\sum_{q\in 2^{|C^{\prime}_{i}|}}no_{i,q}=no_{i}$
$\displaystyle\forall i\in[p]$ (3.5) $\displaystyle\sum_{w\in
U^{\prime}}e_{wv}+\sum_{i\in[p]}no_{i,q}b^{i,q}_{v}\neq\sum_{w\in
U^{\prime}}e_{wu}+\sum_{i\in[p]}no_{i,q}b^{i,q}_{u}$ $\displaystyle\forall
u,v\in U^{\prime}$ (3.6) $\displaystyle d^{i,q}_{v}\neq\sum_{w\in
U^{\prime}}e_{wu}+\sum_{i\in[p]}no_{i,q}b^{i,q}_{u}$ $\displaystyle\forall
e^{i,q}_{u,v}=1\text{ and }(i,q)\in S_{1}$ (3.7)

Assume that we have found the values $no_{i,q}$ for $(i,q)$, $i\in[p]$,
$q\in[2^{|C^{\prime}_{i}|}]$. We construct an optimal vertex-irregulator of
$G[V\setminus S^{\prime}]$ as follows. Start with an empty set $S^{*}$. For
each $i\in[p]$ take all components $C_{j}$ of type $i$. Partition them in to
$2^{|C^{\prime}_{i}|}$ sets $\mathcal{C}^{i}_{q}$ such that any set
$q\in[2^{|C^{\prime}_{i}|}]$ contains exactly $no_{i,q}$ of these components.
For any component $C\in\mathcal{C}^{i}_{q}$, select all vertices represented
by the set $S^{i}_{q}$ (as it was defined before) and add them to $S^{*}$. The
final $S^{*}$ is an optimal vertex-irregulator for $G[V\setminus S^{\prime}]$.

Let $S=S^{\prime}\cup S^{*}$. We show that $S$ is a vertex-irregulator of $G$.
To do so, it suffices to verify that in the graph $G[V\setminus S]$ there are
no two adjacent vertices with the same degree. Let $u,v$ be a pair of adjacent
vertices in a component represented by $C^{\prime}_{i}\setminus S$, which is
of type $(i,q)$. If $d_{G[V\setminus S]}(u)=d_{G[V\setminus S]}(v)$, then
$(i,q)\in S_{2}$. Therefore, $no_{i,q}=0$ and we do not have such a component
in $G[V\setminus S]$. Thus, it suffices to focus on adjacent vertices such
that at least one of them is in $U^{\prime}$. Notice that, in $G[V\setminus
S]$, the degree of vertex $u\in U^{\prime}$ is equal to $\sum_{w\in
U^{\prime}}e_{wv}+\sum_{i\in[p]}no_{i,q}b^{i,q}_{v}$. In other words, no two
adjacent vertices in $U^{\prime}$ have the same degree due to the constrain
3.6. Lastly, the constrain 3.7 guarantees that no vertex in $U^{\prime}$ is
adjacent to a vertex in $C_{i}\setminus S$ (for some $i\in[p]$) such that both
of them have the same degree in $G[V\setminus S]$. Moreover, both $S^{\prime}$
and $S^{*}$ are constructed to be minimum such sets. Thus, $S$ is an optimal
vertex-irregulator of $G$. Finally, since the number of variables in the model
is bounded by a function of $k$, we can and obtain $S^{*}$ in FPT time,
parameterised by $k$ (by running for example the Lenstra algorithm [26]). ∎

The previous algorithm can be used to find an optimal vertex-irregulator of a
graph $G$ in FPT-time when parameterised by the cluster deletion number of
$G$. Note that the cluster deletion number of a graph can be computed in FPT-
time parameterised by $k$ [20].

######  Definition 3.5 ( [20]).

Let $G=(V,E)$ be a graph and $S\subseteq V$ be a set of minimum order such
that all the connected components of $G[V\setminus S]$ are cliques. Then $G$
has _cluster deletion number_ $k$, where $k=|S|$.

######  Theorem 3.6.

Given a graph $G=(V,E)$ with cluster deletion number $k$, there exists an
algorithm that computes ${\rm I}_{v}(G)$ in FPT-time parameterised by $k$.

###### Proof.

Let $S$ be such that $|S|=k$ and $G[V\setminus S]$ is a disjoint union of
cliques $C_{1},\dots C_{m}$ for $m\geq 1$. Our goal is to reduce the size of
these cliques so that each one of them has order at most $2^{k}$. We achieve
this through the the following procedure. Let $i\in[m]$ be such that the
clique $C_{i}=(V_{C_{i}},E_{C_{i}})$ has $|V_{C_{i}}|>2^{k}$. Let
$V_{1},\dots,V_{p}$ be the partition of $V_{C_{i}}$ defined by the twin
equivalence of $C_{i}$. That is, two vertices $u,v\in V_{C_{i}}$ belong in a
$V_{j}$, $j\in[p]$, if and only if $u$ and $v$ are twins. Note that $p\leq
2^{k}$. Observe that, since $C_{i}$ is a clique, the graphs $C_{i}[V_{j}]$,
$j\in[p]$, are also cliques. In other words, for each $j\in[p]$, all the
vertices of $V_{j}$ are adjacent twins. We delete all but one vertex of
$V_{j}$, for each $j\in[p]$, and repeat this process for every $i\in[m]$ such
that $|V_{C_{i}}|>2^{k}$. Let $G^{\prime}=(V^{\prime},E^{\prime})$ be the
resulting subgraph of $G$ and $d=|D|$, where $D$ is the set of vertices that
were removed throughout this process. It follows from Lemma 2.3 that ${\rm
I}_{v}(G)={\rm I}_{v}(G^{\prime})+d$. Observe also that $S\subseteq
V^{\prime}$ and that each connected component of
$G^{\prime}[V^{\prime}\setminus S]$ is a clique of at most $2^{k}$ vertices.
In other words, $G^{\prime}$ has vertex integrity at most $2^{k}+k$. To sum
up, to compute ${\rm I}_{v}(G)$ it suffices to compute ${\rm
I}_{v}(G^{\prime})$, which can be done in FPT-time by running the algorithm
presented in Theorem 3.4. ∎

##  4 Edge-irregulators

In this section we begin the study of finding an optimal edge-irregulator of a
given graph $G$. It turns out that the decision version of this problem is
$\mathcal{NP}$-complete, even for quite restrictive classes of graphs.
Furthermore, it is also ${\rm W}[1]$-hard parameterised by the size of the
solution.

######  Theorem 4.1.

Let $G$ be a graph and $k\in\mathbb{N}$. Deciding if ${\rm I}_{e}(G)\leq k$ is
$\mathcal{NP}$-complete, even if $G$ is a planar bipartite graph of maximum
degree $4$.

###### Proof.

The problem is clearly in $\mathcal{NP}$. We focus on showing it is also
$\mathcal{NP}$-hard. This is achieved through a reduction from the Planar
3-SAT problem which is known to be $\mathcal{NP}$-complete [18]. In that
problem, a 3CNF formula $\phi$ is given as an input. We say that a bipartite
graph $G^{\prime}=(V,C,E)$ _corresponds_ to $\phi$ if it is constructed from
$\phi$ in the following way: for each literal $x_{i}$ (resp. $\lnot x_{i}$)
that appears in $\phi$, add the _literal vertex_ $v_{i}$ (resp.
$v^{\prime}_{i}$) in $V$ (for $1\leq i\leq n$) and for each clause $C_{j}$ of
$\phi$ add a _clause vertex_ $c_{j}$ in $C$ (for $1\leq j\leq m$). Then the
edge $v_{i}c_{j}$ (resp. $v^{\prime}_{i}c_{j}$) is added if the literal
$x_{i}$ (resp. $\lnot x_{i}$) appears in the clause $C_{j}$. Finally, we add
the edge $v_{i}v^{\prime}_{i}$ for every $i$. A 3CNF formula $\phi$ is valid
as input to the Planar 3-SAT problem if the graph $G^{\prime}$ that
corresponds to $\phi$ is planar. Furthermore, we may assume that each variable
appears in $\phi$ twice as a positive and once as a negative literal. The
question is whether there exists a truth assignment to the variables of $X$
satisfying $\phi$.

Starting from a 3CNF formula $\phi$, we construct a graph $G$ such that ${\rm
I}_{e}(G)\leq 3n$ if and only if $\phi$ is satisfiable. The construction of
$G$ is as follows: we start with the graph $G^{\prime}$ that corresponds to
$\phi$. Then, for each $1\leq i\leq n$, we remove the edge
$v_{i}v^{\prime}_{i}$, and attach the gadget illustrated in Figure 2 to
$v_{i}$ and $v^{\prime}_{i}$. Let $E_{i}$ denote the edges of the gadget
attached to $v_{i}$ and $v^{\prime}_{i}$ plus the edges $e_{i}^{1},e_{i}^{2}$
and $e_{i}^{3}$. Finally, for each $1\leq j\leq m$, we add the star on $5$
vertices, and identify one of its leaves with the vertex $c_{j}$. Observe that
the resulting graph $G$ is planar, bipartite and $\Delta(G)=4$.

Before we provide the reduction, let us show two claims that are going to be
useful.

######  Claim 4.2.

Let $S$ be an edge-irregulator of $G$ such that $|S|\leq 3n$. For every $1\leq
i\leq n$, we have that $|S\cap E_{i}|\geq 3$.

Proof of the claim. Observe that
$d_{G}(u_{5})=d_{G}(v_{i})=d_{G}(u_{6})=d_{G}(u_{7})$. It follows that $S$
contains at least one edge $a_{1}$ incident to $u_{6}$ or $u_{7}$ and one edge
$a_{2}$ incident to $v_{i}$ or $u_{5}$. We distinguish cases:

    1. 1.

$a_{1}=a_{2}=v^{\prime}_{i}u_{6}$. Then $S$ also contains an edge $a_{3}$
incident to $v_{i}$ or $u_{5}$. If $a_{3}=u_{5}v^{\prime}_{i}$, then $S$
contains an additional edge incident to $u_{2}$ or $u_{5}$. If
$a_{3}=u_{5}u_{4}$, then $S$ also contains the edge $u_{3}u_{4}$. If
$a_{3}=u_{2}u_{5}$, then $S$ contains at least one additional edge incident to
$u_{2}$ and $u_{1}$. If $a_{3}=u_{5}v_{i}$, then $S$ contains one additional
edge incident to $u_{2}$ or $u_{5}$. In any one of the above cases, we have
that $|S_{i}|\geq 3$. Thus, we may assume that $a_{3}$ is incident to $v_{i}$
but not to $u_{5}$. If $a_{3}=e_{i}^{1}$ or $a_{3}=e_{i}^{2}$, then $S$
contains an additional edge incident to $v_{i}$ or $u_{6}$. Finally, if
$a_{3}=v_{i}u_{6}$, then $S$ contains an additional edge incident to $u_{6}$
or $u_{8}$. Thus, if $a_{1}=a_{2}=v^{\prime}_{i}u_{6}$, then $|S_{i}|\geq 3$.

    2. 2.

$a_{1}\neq a_{2}$. We distinguish some additional cases:

      1. (a)

$a_{1}=v_{i}u_{6}$. If
$a_{2}\in\\{e_{i}^{3},v^{\prime}_{i}u_{9},v^{\prime}_{i}u_{5}\\}$, then $S$
contains an additional edge incident to $u_{7}$. If
$a_{2}\in\\{v_{i}u_{5},u_{5}u_{4}\\}$, then $S$ contains an additional edge
incident to $u_{2}$. Finally, if $a_{2}=u_{5}u_{4}$, then $S$ contains an
additional edge incident to $u_{3}$.

      2. (b)

$a_{1}=u_{6}u_{7}$. Then $S$ contains an additional edge incident to $u_{9}$.

      3. (c)

$a_{1}\in\\{u_{7}u_{9},u_{7}u_{10},u_{7}u_{11}\\}$. Then $S$ contains an
additional edge incident to $u_{7}$.

      4. (d)

$a_{1}=u_{6}u_{8}$. Then $S$ contains an additional edge incident to $u_{16}$.

Thus, if $a_{1}\neq a_{2}$, then $|S_{i}|\geq 3$, which finishes the proof of
the claim.

$\diamond$

######  Claim 4.3.

Let $S$ be an edge-irregulator of $G$ such that $|S|\leq 3n$. Then, for every
$1\leq i\leq n$, we have that

    * –

if $|S\cap\\{e_{i}^{1},e_{i}^{2}\\}|\geq 1$ then
$|S\cap\\{e_{i}^{3},e_{i}^{4}\\}|=0$ and

    * –

if $|S\cap\\{e_{i}^{3},e_{i}^{4}\\}|\geq 1$ then
$|S\cap\\{e_{i}^{1},e_{i}^{2}\\}|=0$.

Proof of the claim. Since the proofs of the two items are highly symmetrical,
we will only prove the first item. To do that, it suffices to show that if $S$
does not respect the statement for some $1\leq i\leq n$, then $|S\cap
E_{i}|\geq 4$. Then, since $|S|\leq 3n$, and $1\leq i\leq n$, there exists a
$1\leq j\leq n$ such that $i\neq j$ and $|S\cap E_{j}|\leq 2$. This
contradicts Claim 4.2.

Let $H=G-S$. Assume first that there exists an $i$ such that, say,
$e_{i}^{1}\in S$ and $e_{i}^{3}\in S$. Observe that $S$ contains at least one
edge $e$ incident to $u_{6}$ or $u_{7}$, as otherwise we would have that
$d_{H}(u_{6})=d_{H}(u_{7})$, contradicting the fact that $S$ is an edge-
irregulator of $G$. Thus, if we also have that $e_{i}^{2}\in S$ or that
$e_{i}^{4}\in S$, it follows that $|S\cap E_{i}|\geq 4$, a contradiction.
Thus, we may assume that $S\cap E_{i}=\\{e_{i}^{1},e_{i}^{3},e\\}$. If
$e\in\\{u_{7}u_{9},u_{7}u_{10},u_{11}\\}$, say $e=u_{7}u_{9}$, then
$d_{H}(u_{7})=d_{H}(u_{10})$. Also, if $e=u_{6}u_{8}$, then $S$ also contains
$u_{8}u_{16}$. Finally, if $e=v_{i}u_{6}$ (resp. $e=u_{6}v^{\prime}_{i})$ then
$d_{H}(u_{6})=d_{H}(v^{\prime}_{i})$ (resp. $d_{H}(u_{6})=d_{H}(v_{i})$). It
follows from Observation 2.1 that in all cases, we have that $|S\cap
E_{i}|\geq 4$, a contradiction. $\diamond$

We are now ready to give the reduction. Let $G$ be the graph constructed from
the formula $\phi$ as explained above. We show that there exists a satisfying
truth assignment of $\phi$ if and only if ${\rm I}_{e}(G)\leq 3n$.

For the first direction, let $T$ be a satisfying truth assignment of $\phi$.
Let $S$ be the set containing the edges $e_{i}^{1},e_{i}^{2},u_{6}u_{7}$ for
every $1\leq i\leq n$ such that $T(x_{i})=true$ and the edges
$e_{i}^{3},e_{i}^{4},v_{i}u_{6}$ for each $i$ such that $T(\lnot x_{i})=true$.
Let $H=G-S$. Clearly, $|S|=3n$. Also $S$ is an edge-irregulator of $G$.
Indeed, the part of the graph $H$ that corresponds to the gadget attached to
$v_{i}$ and $v^{\prime}_{i}$ is clearly locally irregular for every $i$. Also,
for each $j$, we have that $d_{H}(c_{j})\leq 3$ (since $C_{j}$ is satisfied by
at least one literal) and any vertex in $N_{H}(c_{j})$ has degree equal to
$4$.

For the reverse direction, assume that ${\rm I}_{e}(G)\leq 3n$ and let $S$ be
an edge-irregulator of $G$ such that $|S|=3n$. Recall that due to Claim 4.3,
for each $i\in[n]$, if $S$ contains one edge in $\\{e_{i}^{1},e_{i}^{2}\\}$
then it contains no edge in $\\{e_{i}^{3},e_{i}^{4}\\}$ and _vice versa_. For
each $i\in[n]$, we set $T(x_{i})=true$ if $S$ contains one edge in
$\\{e_{i}^{1},e_{i}^{2}\\}$ and $T(\lnot x_{i})=true$ in any other case. We
claim that $T$ is indeed a truth assignment that satisfies $\phi$. Indeed, due
to Claim 4.3, we know that each variable will receive exactly one truth value.
Also, since $S$ is an edge-irregulator, and due to Claim 4.2, we know that for
each $j\in[m]$, there exists an $i\in[n]$ such that either $v_{i}c_{j}\in S$
or $v^{\prime}_{i}c_{j}\in S$; that is, for each clause $C_{j}$, there exists
either a literal $x_{i}$ or a literal $\lnot x_{i}$ that has been set to true.
In other words, each clause of $\phi$ is satisfied by $T$. This ends the
reduction. ∎

$u_{1}$$u_{3}$$u_{2}$$u_{4}$$u_{5}$$v^{\prime}_{i}$$v_{i}$$u_{6}$$u_{8}$$u_{7}$$u_{11}$$u_{10}$$u_{9}$$e_{i}^{4}$$e_{i}^{2}$$e_{i}^{1}$$e_{i}^{3}$$c_{j}$
Figure 2: The construction in the proof of Theorem 4.1. The dashed lines are
used to represent the edges between the literal and the clause vertices.

######  Theorem 4.4.

Let $G$ be a graph and $k\in\mathbb{N}$. Deciding if ${\rm I}_{e}(G)\leq k$ is
${\rm W}[1]$-hard parameterised by $k$.

###### Proof.

The reduction is from $k$-Multicoloured Clique.

Input: A graph $G^{\prime}=(V,E)$ and a partition $(V_{1},\ldots,V_{k})$ of
$V$ into $k$ independent sets. Question: Does there exist a set $S\subseteq V$
such that $G^{\prime}[S]$ is a clique? $k$-Multicoloured Clique

It is known that $k$-Multicoloured Clique is ${\rm W}[1]$-hard parameterised
by $k$ [14].

On a high level, our reduction will proceed as follows. Starting with the
graph $G^{\prime}$ that is given in the input of $k$-Multicoloured Clique, we
will first subdivide every edge of the graph $G^{\prime}$. Then, for each
$i\in[k]$, we will attach one copy of a particular gadget to the vertices of
$V_{i}$. Also, for each $1\leq i<j\leq k$, we will attach a copy of our gadget
to the vertices that correspond to the edges $v_{i}v_{j}$ of $G^{\prime}$,
with $v_{i}\in V_{i}$ and $v_{j}\in V_{j}$. In total, we will add
$(k^{2}+k)/2$ gadgets.

The gadgets are structured so that any edge-irregulator of the graph contains
at least one edge for each gadget (so any solution has a size of at least
$(k^{2}+k)/2$). Furthermore, we prove that, if we have selected only one edge
from a gadget, then that edge must be incident to either a vertex of the
original graph or a vertex that represents an edge of the original graph.
Finally, we show that:

    * –

an edge-irregulator $S$ that contains exactly one edge from each gadget (i.e.
an edge-irregulator of size $(k^{2}+k)/2$) can give us a clique of size $k$ in
the original graph by selecting the vertices and edges (represented by
vertices) of the original graph that are incident to the edges of $S$ and

    * –

if we have a clique of size $k$ in the original graph we can construct an
optimal edge-irregulator $S$ by selecting the edges of the gadgets that are
incident to the $k$ vertices of the clique and the $(k^{2}-k)/2$ vertices that
represent the edges of the clique.

We proceed with the formal proof. Assume that we are given an instance
$G^{\prime}=(V,E)$ with vertex partition $(V_{1},\ldots,V_{k})$ where
$|V_{i}|=n$ for all $i\in[k]$. For each $i\in[k]$, we denote by $v_{i}^{p}$,
for $p\in[n]$, the vertices of $V_{i}$. We construct a graph $G$ as follows:

    * –

Start with a copy of $G^{\prime}$.

    * –

Subdivide each edge $e\in E$. Let $u_{i,j}^{p,q}$ be the vertex that
corresponds to the edge $v_{i}^{p}v_{j}^{q}\in E$. Also, let $U_{i,j}$ be the
set of vertices that corresponds to the edges between the sets $V_{i}$ and
$V_{j}$, _i.e._ , the set $\\{u_{i,j}^{p,q}\mid v_{i}^{p}v_{j}^{q}\in E\\}$.

    * –

For each pair $(i,j)$ where $1\leq i<j\leq k$, create a copy of the gadget
$H_{|U_{i,j}|}$, illustrated in Figure 3, and add all the edges between the
copy of $w$ and the vertices of $U_{i,j}$. We denote this copy of $w$ by
$w_{i,j}$, the copy of $H_{|U_{i,j}|}$ by $H^{w_{i,j}}$ and the copy of $y$ in
$H^{w_{i,j}}$ by $y_{i,j}$.

    * –

For each $i\in[k]$, create a copy of the gadget $H_{|V_{i}|}$ and add all the
edges between the copy of $w$ and the vertices of $V_{i}$. We denote this copy
of $w$ by $w_{i}$, the copy of $H_{|V_{i}|}$ by $H^{w_{i}}$ and the copy of
$y$ in $H^{w_{i}}$ by $y_{i}$.

    * –

Finally, add leaves attached to the vertices of $V_{i}$, $i\in[k]$, so that
each vertex of $V_{i}$ has degree $kn$ and attached to the vertices of
$U_{i,j}$, $1\leq i<j\leq k$, so each that vertex of $U_{i,j}$ has degree
$kn+1$.

Let $G$ be the resulting graph.

$w$$y$$\,\dots$Set $V_{i}$ for $i\in[k]$ or $U_{i,j}$ for $1\leq i<j\leq
k$$\,\dots$$n^{2}-2$ leaves$\,\dots$$n^{2}-1$ leaves$\,\dots$$n^{2}-1$
leaves$n^{2}-b$ times$\,\dots$

Figure 3: The gadget $H_{b}$ used in the proof of Theorem 4.4. The black
vertices represent the vertices of the gadget. The white vertices represent
either a set of the original vertices $V_{i}$, $i\in[k]$, or a set of edge
vertices $U_{i,j}$, $1\leq i<j\leq k$. In the construction, if $w$ is adjacent
to vertices of a $V_{i}$, $i\in[k]$, then $b=|V_{i}|$ while if $w$ is adjacent
to vertices of a $U_{i,j}$, $1\leq i<j\leq k$, then $b=|U_{i,j}|$. In each
copy of the gadget the degrees of $w$ and $y$ are equal.

We prove that $G$ has an edge-irregulator of order $(k^{2}+k)/2$ if and only
if $G^{\prime}$ is a yes instance of $k$-Multicoloured Clique.

Assume that $G^{\prime}$ is a yes instance of $k$-Multicoloured Clique and
$C=\\{c_{1},\ldots,c_{k}\\}$ is a clique in $G^{\prime}$ with $c_{i}\in V_{i}$
for every $i\in[k]$. We will construct an edge-irregulator of $G$ as follows.
Start with an empty set $S$. Notice that, for each $i\in[k]$, $|V_{i}\cap
C|=1$ and let $p\in[n]$ be such that $v_{i}^{p}=c_{i}$; we add to $S$ the edge
$v_{i}^{p}w_{i}$. For each pair $(i,j)$, $1\leq i<j\leq k$, let $p,q\in[n]$ be
such that $v_{i}^{p}=c_{i}$ and $v_{j}^{q}=c_{j}$; we add to $S$ the edge
$u_{i,j}^{p,q}w_{i,j}$. Notice the edge $v_{i}^{p}v_{j}^{q}$ must exist in $E$
since $C$ is a clique. It follows that the vertex $u_{i,j}^{p,q}$, and
therefore the edge $u_{i,j}^{p,q}w_{i,j}$, also exists in $G$. By
construction, $|S|=(k^{2}+k)/2$. It only remains to prove that $S$ is an edge-
irregulator of $G$.

Consider the graph $G-S$. Observe that, for every $H^{w_{i}}$, $i\in[k]$, we
have reduced the degree of $w_{i}$ by exactly one. Therefore, any two adjacent
vertices of $H^{w_{i}}$ have different degree (see Figure 3). The same holds
true for every $H^{w_{i,j}}$, $1\leq i<j\leq k$. Consider now the edges $xz\in
E(G)$ such that $x\in\\{w_{i},w_{j},w_{i,j}\\}$, and $z\in V_{i}\cup
U_{i,j}\cup V_{j}$, $1\leq i<j\leq k$. Notice that $d_{G-S}(x)=n^{2}-1$ and
$kn-1\leq d_{G-S}(z)\leq kn+1$. For sufficiently large $n$, we have that
$n^{2}-1>kn+1$. It remains to consider the edges between vertices in
$V_{i}\cup V_{j}$ and in $U_{i,j}$ for any $1\leq i<j\leq k$. Notice that, for
every $1\leq i<j\leq k$, all vertices of $V_{i}\cup V_{j}$, except one vertex
$v_{i}^{p}\in V_{i}$ and one vertex $v_{j}^{q}\in V_{j}$, have degree $kn$,
and $d_{G-S}(v_{i}^{p})=d_{G-S}(v_{j}^{q})=kn-1$. Also, all vertices of
$U_{i,j}$, except one vertex $u^{\prime}$, have degree $kn+1$, and
$d_{G-S}(u^{\prime})=kn$. So, $u^{\prime}$ is the only vertex of $U_{i,j}$
that could possibly have the same degree as a vertex in
$V_{i}\setminus\\{v_{i}^{p}\\}$ or $V_{j}\setminus\\{v_{j}^{q}\\}$. It follows
by the construction of $S$ that $u^{\prime}$ is actually $u_{i,j}^{p,q}$.
Also, by the construction of $G$, $u_{i,j}^{p,q}$ is adjacent only to
$v_{i}^{p}$ and $v_{j}^{q}$, as it represents the edge between their
corresponding vertices in $G^{\prime}$. Thus, for every $1\leq i<j\leq k$, no
vertex in $U_{i,j}$ has the same degree as any of its neighbours in $V_{i}$ or
$V_{j}$. It follows from all the arguments above that $S$ is indeed an edge-
irregulator of $G$.

Now we show that if ${\rm I}_{e}(G)=(k^{2}+k)/2$ then $G^{\prime}$ has a
clique of size $k$. Let $S$ be an edge-irregulator of $G$ of order
$(k^{2}+k)/2$. First, we notice that for each $i\in[k]$,
$d_{G}(w_{i})=d_{G}(y_{i})$ and that for each $1\leq i<j\leq k$,
$d_{G}(w_{i,j})=d_{G}(y_{i,j})$. Let $E_{w_{i}}$ be the set of edges $w_{i}v$
for $v\in V_{i}$ and $E_{w_{i,j}}$ be the set of edges $w_{i,j}u$ for $u\in
U_{i,j}$. Also, let $w\in\\{w_{i}\mid i\in[k]\\}\cup\\{w_{i,j}\mid 1\leq
i<j\leq k\\}$. Since $S$ is an edge-irregulator of $G$, it follows that
$|S\cap(E(H^{w})\cup E_{w})|\geq 1$. Also, observe that for any pair of
distinct vertices $w,w^{\prime}\in\\{w_{i}\mid i\in[k]\\}\cup\\{w_{i,j}\mid
1\leq i<j\leq k\\}$, we have that $(E(H^{w})\cup
E_{w})\cap(E(H^{w^{\prime}})\cup E_{w^{\prime}})=\emptyset$. Thus, and since
$|S|=(k^{2}+k)/2$, we obtain that, actually, $|S\cap(E(H^{w})\cup E_{w})|=1$.
Next, we show that $S$ includes only edges from the set $E_{w}$, for each
$w\in\\{w_{i}\mid i\in[k]\\}\cup\\{w_{i,j}\mid 1\leq i<j\leq k\\}$. In
particular we claim the following:

######  Claim 4.5.

Let $w\in\\{w_{i}\mid i\in[k]\\}\cup\\{w_{i,j}\mid 1\leq i<j\leq k\\}$. It
holds that $S\cap E(H^{w})=\emptyset$ and that $|S\cap E_{w}|=1$.

Proof of the claim. Assume that $S\cap E(H^{w})\neq\emptyset$ and let $e\in
S\cap E(H^{w})$. We distinguish cases according to which edge of $H^{w}$ is
$e$. In each case, we show that $S$ must include an additional edge of
$E(H^{w})$, which is a contradiction to the fact that $|S\cap(E(H^{w})\cup
E_{w})|=1$.

$\boldsymbol{e}$ is incident to neither $\boldsymbol{w}$ nor $\boldsymbol{y}$:
Then $S$ must also include an additional edge incident to $w$ or $y$ (from
previous discussion).

$\boldsymbol{e}$ is incident to $\boldsymbol{y}$: Then, $S$ must include an
additional edge of $E(H^{w})$, as otherwise $d_{G-S}(y)=d-1$ and $y$ would
have at least one neighbour of degree $d-1$.

$\boldsymbol{e}$ is incident to $\boldsymbol{w}$ and $\boldsymbol{e\neq wy}$:
Then, $S$ must include an additional edge of $E(H)$, as otherwise $G-S$ would
include a connected component isomorphic to $K_{2}$. $\diamond$
The previous claim also shows that
$S\subseteq\bigcup_{i\in[k]}E_{w_{i}}\cup\bigcup_{1\leq i<j\leq
k}E_{w_{i,j}}$.

We now explain how to construct a clique of $G^{\prime}$ of order $k$. Let
$\ell(i)=m(i)$ be the index that specifies which edge incident to $w_{i}$ is
included in $S$. That is, $\ell(i)$ is such that $w_{i}v_{i}^{\ell(i)}\in S$.
Similarly, for each $1\leq i<j\leq k$, let $\ell(i,j)$ and $m(i,j)$ be the
indices such that $w_{i,j}u_{i,j}^{\ell(i,j),m(i,j)}\in S$. Notice that both
$\ell(i)$ and $\ell(i,j)$ are unique as $S$ contains exactly one edge incident
to each of $w_{i}$ and $w_{i,j}$ (by Claim 4.5).

######  Claim 4.6.

The set $C=\\{v_{i}^{\ell(i)}\mid i\in[k]\\}$ induces a clique of order $k$ in
$G$.

Proof of the claim. First, for any $1\leq i<j\leq k$, we show that
$\ell(i)=\ell(i,j)$ and $m(j)=m(i,j)$. To simplify the notation let
$\ell=\ell(i,j)$ and $m=m(i,j)$. By the definition of $\ell$ and $m$ we have
that $w_{i,j}u_{i,j}^{\ell,m}\in S$. Now, we consider the degrees of the
vertices $v_{i}^{\ell}$ and $u_{i,j}^{\ell,m}$. Since
$w_{i,j}u_{i,j}^{\ell,m}\in S$, we have that $d_{G-S}(u_{i,j}^{\ell,m})=kn$.
If $\ell(i)\neq\ell$, then $d_{G-S}(v_{i}^{\ell})=kn$, as $S$ would not
include any edges incident to $v_{i}^{\ell}$ in that case. This is a
contradiction since $v_{i}^{\ell}$ and $u_{i,j}^{\ell,m}$ are adjacent in $G$
(by construction) and remain so in $G-S$ (as
$S\subseteq\bigcup_{i\in[k]}E_{w_{i}}\cup\bigcup_{1\leq i<j\leq
k}E_{w_{i,j}}$). Therefore, for any $1\leq i<j\leq k$,
$\ell(i)=\ell=\ell(i,j)$. Similarly, we can show that for any $1\leq i<j\leq
k$, $m(j)=m=m(i,j)$. Now we show that for every pair of distinct vertices
$u,v\in\\{v_{i}^{\ell(i)}\mid i\in[k]\\}$, we have that $u$ and $v$ are
adjacent in $G^{\prime}$. W.l.o.g. let $u=v_{i}^{\ell(i)}$ and
$v=v_{j}^{\ell(j)}$ for some $1\leq i<j\leq k$. We know that $\ell(i)=\ell$
and $\ell(j)=m(j)=m$. Therefore, the vertex
$u_{i,j}^{\ell(i,j),m(i,j)}=u_{i,j}^{\ell,m}$ of $G$ is adjacent to
$v_{i}^{\ell(i)}$ and $v_{j}^{\ell(j)}$. This means that $v_{i}^{\ell(i)}$ and
$v_{j}^{\ell(j)}$ are incident in $G^{\prime}$ as the vertex
$u_{i,j}^{\ell(i),m(j)}$ corresponds to the edge between these two vertices in
$G^{\prime}$ (recall the construction of $G$). Thus, any pair of vertices in
$C$ is a pair of adjacent vertices in $G^{\prime}$. It follows that $C$ is a
clique. $\diamond$
This completes the proof. ∎

Unfortunately, this problem exhibits a similar behaviour to finding optimal
vertex-irregulators, as it also remains intractable even for “relatively
large” structural parameters.

######  Theorem 4.7.

Let $G$ and $k\in\mathbb{N}$. Deciding if ${\rm I}_{e}(G)\leq k$ is ${\rm
W}[1]$-hard parameterised by either the feedback vertex set number or the
treedepth of $G$.

###### Proof.

The reduction is from the General Factor problem:

Input: A graph $H=(V,E)$ and a list function
$L:V\rightarrow\mathcal{P}(\\{0,\dots,\Delta(H)\\})$ that specifies the
available degrees for each vertex $u\in V$. Question: Does there exist a set
$S\subseteq E$ such that $d_{H-S}(u)\in L(u)$ for all $u\in V$? General Factor

This problem is known to be ${\rm W}[1]$-hard when parameterised by the vertex
cover number of $H$ [19].

Starting from an instance $(H,L)$ of General Factor, we construct a graph $G$
such that ${\rm I}_{e}(G)\leq n^{2}$, where $n=|V(H)|$, if and only if $(H,L)$
is a yes-instance. For every vertex $u\in V(H)$, let us denote by
$\overline{L}(u)$ the set $\\{0,1,\ldots,d_{H}(u)\\}\setminus L(u)$. In the
case where $\\{0,1,\ldots,d_{H}(u)\\}\setminus L(u)=\emptyset$, we set
$\overline{L}(u)=\\{-1\\}$. On a high level, the graph $G$ is constructed by
adding some trees on the vertices of $H$. In particular, for each vertex $u\in
V(H)$ and for each element $a$ in $\overline{L}(u)$, we will attach a tree to
$u$ whose purpose is to prevent $u$ from having degree $a$ in $G-S$, for any
optimal edge-irregulator $S$ of $G$.

We begin by defining an arbitrary order on the vertices of $H$. That is,
$V(H)=\\{u_{1},u_{2},\dots,u_{n}\\}$. Next, we describe the trees we will use
in the construction of $G$. In particular, we will describe the trees that we
attach to the vertex $u_{i}$, for every $1\leq i\leq n$. First, for each
$a_{j}\in\overline{L}(u_{i})$, define the value
$a^{\prime}_{j}=d_{H}(u_{i})-a_{j}$. Also, for each $j$, let
$d_{i,j}=2in^{4}-a^{\prime}_{j}$. For each “forbidden degree” $a_{j}$ in the
list $\overline{L}(u_{i})$, we will attach a tree $T_{i,j}$ to $u_{i}$. We
define the tree $T_{i,j}$ as follows.

$u_{i,j}$$u_{i}$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$\,\dots$$d_{i,j}-1$$d_{i,j}-1$$n^{2}$$d_{i,j}-2$$d_{i,j}-2$$n^{2}$$d_{i,j}-n^{2}$$d_{i,j}-n^{2}$$n^{2}+d$$2in^{4}-a_{j}$

Figure 4: The tree $T_{i,j}$ that is attached to the vertex $u_{i}$, where $j$
is such that $a_{j}\in\overline{L}(u_{i})$, in the proof of Theorem 4.7. The
value of $d$ is such that, in total, $d(u_{i,j})=2in^{4}-a_{j}+1$.

First, for every $0\leq k\leq n^{2}-1$, create $n^{2}$ copies of
$S_{d_{i,j}-k}$ (the star on $d_{i,j}-k$ vertices) and $q$ additional copies
of $S_{d_{i,j}-n^{2}+1}$ (the exact value of $q$ will be defined in what
follows). Then, choose one leaf from each one of the above stars, and identify
them into a single vertex denoted as $u_{i,j}$; the value of $q$ is such that
$d(u_{ij})=d_{i,j}-1=2in^{4}-a^{\prime}_{j}-1$. Let $T_{i,j}$ be the resulting
tree and let us say that $u_{i,j}$ is the root of $T_{i,j}$.

Let us now describe the construction of $G$. For each vertex $u_{i}\in V(H)$
and for each $a_{j}\in\overline{L}(u_{i})$, add the tree $T_{i,j}$ to $H$ and
the edge $u_{i,j}u_{i}$. Then, for each vertex $u_{i}\in V(H)$, for any $j$
such that $u_{i,j}$ is a neighbour of $u_{i}$, add $p_{i}$ additional copies
of the tree $T_{i,j}$, as well as the edges between $u_{i}$ and the roots of
the additional trees, so that $d_{G}(u_{i})=2in^{4}$. The resulting graph is
$G$. Note that, for each vertex of $V(H)$, we are adding at most
$\mathcal{O}(n^{4})$ trees, each tree containing $\mathcal{O}(n^{4})$
vertices. Thus, the construction of $G$ is achieved in polynomial time.

We are now ready to present our reduction. Assume first that $(H,L)$ is a yes-
instance of General Factor, and let $S\subseteq E$ be such that $d_{H-S}(u)\in
L(u)$ for all $u\in V(H)$. We claim that $S$ is also an edge-irregulator of
$G$. By the construction of $G$, and since $S$ only contains edges from $H$,
there are no two adjacent vertices in $G-H$ that have the same degree in
$G-S$. Thus, it remains to check the pairs of adjacent vertices $x,y$ such
that, either both $x$ and $y$ belong to $V(H)$, or, w.l.o.g., $x\in V(H)$ and
$y\in V(G-H)$. For the first case, let $x=u_{i}$ and $y=u_{i^{\prime}}$, for
$1\leq i<i^{\prime}\leq n$. Then, assuming that
$d_{G-S}(u_{i})=d_{G-S}(u_{i^{\prime}})$, we get that
$2in^{4}-p=2i^{\prime}n^{4}-p^{\prime}$, where $S$ contains $0\leq p\leq
n^{2}$ and $0\leq p^{\prime}\leq n^{2}$ edges incident to $u_{i}$ and
$u_{i^{\prime}}$ respectively. Thus, $2n^{4}(i-i^{\prime})=p-p^{\prime}$, a
contradiction since $-n^{2}\leq p-p^{\prime}\leq n^{2}$ and $-n\leq
i-i^{\prime}\leq n$. For the second case, for every $i$, let
$d_{G-S}(u_{i})=2in^{4}-p$, where the set $S$ contains $1\leq p\leq n^{2}$
edges of $H$ incident to $u_{i}$. Also, by the construction of $G$ and since
$S$ only contains edges from $H$, we have that for every $j$,
$d_{G-S}(u_{i,j})=d_{G}(u_{i,j})=2in^{4}-a^{\prime}_{j}$, where, recall,
$a^{\prime}_{j}=d_{H}(u_{i})-a_{j}$ for $a_{j}\in\overline{L}(u_{i})$. Assume
now that there exist $i,j$ such that $d_{G-S}(u_{i})=d_{G-S}(u_{i,j})$. Then,
$2in^{4}-p=2in^{4}-d_{H}(u_{i})+a_{j}$ and thus $d_{H}(u_{i})-p=a_{j}$. But
then $d_{H-S}(u_{i})=a_{j}$, which is a contradiction since
$a_{j}\in\overline{L}(u_{i})$. Thus, $S$ is an edge-irregulator of $G$ and
$|S|\leq n^{2}$ since $S$ only contains edges of $E(H)$.

For the reverse direction, assume that ${\rm I}_{e}(G)\leq n^{2}$ and let $S$
be an optimal edge-irregulator of $G$. We will show that $S$ is also such that
$d_{H-S}(u_{i})\in L(u_{i})$, for every $i$. Let us first prove the following
claim.

######  Claim 4.8.

Let $S$ be an optimal edge-irregulator of $G$. For every $i,j$, let $T$ be any
copy of the $T_{i,j}$ tree that is attached to $u_{i}$, and let $u$ be the
root of this $T_{i,j}$. If $S$ contains $x\geq 1$ edges of
$E_{i,j}=E(T)\cup\\{uu_{i}\\}$, then $x\geq n^{2}$.

Proof of the claim. Assume there exist $i,j$ such that $|S\cap E_{i,j}|=x\geq
1$ and $x\leq n^{2}$. Among those edges, there are $x_{1}\geq 0$ edges
incident to $u$ and $x_{2}\geq 0$ edges incident to children of $u$ (but not
to $u$), with $x_{1}+x_{2}=x<n^{2}$.

Assume first that $x_{1}=0$. Then $x=x_{2}$ and there is no edge of $S\cap
E_{i,j}$ that is incident to $u$. Then $d_{G-S}(u)=d_{G}(u)$ and observe that
$d_{G}(u)$ is strictly larger than that of any of its children (by the
construction of $G$). It follows that $S\setminus(S\cap E_{i,j})$ is also an
edge-irregulator of $G$, contradicting the optimality of $S$. Thus $x_{1}\geq
1$. It then follows from the construction of $G$ that there exist at least
$n^{2}$ children of $u$, denoted by $z_{1},\dots,z_{n^{2}}$, such that
$d_{G-S}(u)=d_{G}(z_{k})$, for every $1\leq k\leq n^{2}$. Since $x<n^{2}$,
there exists at least one $1\leq k\leq n^{2}$ such that
$d_{G-S}(u)=d_{G-S}(z_{k})$, contradicting the fact that $S$ is an edge-
irregulator. Thus $x\geq n^{2}$. $\diamond$

It follows directly from Claim 4.8 that $S$ contains only edges of $E(H)$.
Assume that there exist $i,j$ such that $d_{H-S}(u_{i})=a_{j}$ and
$a_{j}\in\overline{L}(u_{i})$. Then $d_{G-S}(u_{i})=2in^{4}-a^{\prime}_{j}$.
Also, by the construction of $G$, $u_{i}$ is adjacent to a vertex $u_{i,j}$
for which (since $S$ contains only edges of $E(H)$) we have that
$d_{G-S}(u_{i,j})=d_{G}(u_{i,j})=2in^{4}-a^{\prime}_{j}$. This is
contradicting the fact that $S$ is an edge-irregulator of $G$. Thus, for every
$i,j$, we have that if $d_{H-S}(u_{i})=a_{j}$, then $a_{j}\in L(u_{i})$, which
finishes our reduction.

Finally, if $H$ has vertex cover number $vc$, then, by Observation 2.4, and
since $G$ is constructed by attaching trees of depth $3$ directly on the
vertices of $H$, we have that $G$ has treedepth and feedback vertex set
$\mathcal{O}(vc)$. This concludes our proof. ∎

We close this section by observing that the proof of Theorem 3.4 can be
adapted for the case of edge-irregulators. Indeed, it suffices to replace the
guessing of vertices and the variables defined on vertices, by guessing of
edges and variables defined on the edges of the given graph. Finally, the
definition of the sub-types is done through subgraphs produced only by
deletion of edges. This leads us to the following:

######  Corollary 4.9.

Given a graph $G$ with vertex integrity $k$, there exists an algorithm that
computes ${\rm I}_{e}(G)$ in FPT-time.

##  5 Conclusion

In this work we continued the study of the problem of finding optimal vertex-
irregulators, and introduced the problem of finding optimal edge-irregulators.
In the case of vertex-irregulators, our results are somewhat optimal, in the
sense that we almost characterise exactly which are the “smallest” graph-
structural parameters that render this problem tractable. The only meaningful
parameter whose behaviour remains unknown is the modular-width of the input
graph. The parameterised behaviour of the case of edge-irregulators is also
somewhat understood, but there are still some parameters for which the problem
remains open. Another interesting direction is that of approximating optimal
vertex or edge-irregulators. In particular it would be interesting to identify
parameters for which either problem becomes approximable in FPT-time (recall
that vertex-irregulators are not approximable within any decent factor in
polynomial time [15]). Finally, provided that the behaviour of edge-
irregulators is better understood, we would also like to propose the problem
of finding locally irregular minors, of maximum order, of a given graph $G$.

## References

    * [1] A. Agra, G. Dahl, T. A. Haufmann, and S. J. Pinheiro.  The k-regular induced subgraph problem.  Discretete Applied Mathematics, 222:14–30, 2017.
    * [2] N. Alon, M. Krivelevich, and W. Samotij.  Largest subgraph from a hereditary property in a random graph.  Discrete Mathematics, 346(9):113480, 2023.
    * [3] Y. Asahiro, H. Eto, T. Ito, and E. Miyano.  Complexity of finding maximum regular induced subgraphs with prescribed degree.  Theoretical Computer Science, 550:21–35, 2014.
    * [4] O. Baudon, J. Bensmail, J. Przybyło, and M. Wozniak.  On decomposing regular graphs into locally irregular subgraphs.  European Journal of Combinatorics, 49:90–104, 2015.
    * [5] R. Belmonte and I. Sau.  On the complexity of finding large odd induced subgraphs and odd colorings.  Algorithmica, 83(8):2351–2373, 2021.
    * [6] J. Bensmail.  Maximising 1’s through Proper Labellings.  Research report, 2023.
    * [7] R. Bredereck, S. Hartung, A. Nichterlein, and G. J. Woeginger.  The complexity of finding a large subgraph under anonymity constraints.  In L. Cai, S. Cheng, and T. W. Lam, editors, Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, volume 8283 of Lecture Notes in Computer Science, pages 152–162. Springer, 2013.
    * [8] L. Cai.  Fixed-parameter tractability of graph modification problems for hereditary properties.  Information Processing Letters, 58(4):171–176, 1996.
    * [9] G. Călinescu, C. G. Fernandes, H. Kaul, and A. Zelikovsky.  Maximum series-parallel subgraph.  Algorithmica, 63(1-2):137–157, 2012.
    * [10] M. Chimani, I. Hedtke, and T. Wiedera.  Exact algorithms for the maximum planar subgraph problem: New models and experiments.  ACM J. Exp. Algorithmics, 24(1):2.1:1–2.1:21, 2019.
    * [11] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
    * [12] P. G. Drange, M. S. Dregi, and P. van ’t Hof.  On the computational complexity of vertex integrity and component order connectivity.  Algorithmica, 76(4):1181–1202, 2016.
    * [13] B. C. Esmer, A. Kulik, D. Marx, D. Neuen, and R. Sharma.  Faster exponential-time approximation algorithms using approximate monotone local search.  In S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 50:1–50:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
    * [14] M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen.  On the complexity of some colorful problems parameterized by treewidth.  Inf. Comput., 209(2):143–153, 2011.
    * [15] F. Fioravantes, N. Melissinos, and T. Triommatis.  Complexity of finding maximum locally irregular induced subgraphs.  In A. Czumaj and Q. Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands, volume 227 of LIPIcs, pages 24:1–24:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
    * [16] F. V. Fomin, S. Gaspers, D. Lokshtanov, and S. Saurabh.  Exact algorithms via monotone local search.  J. ACM, 66(2):8:1–8:23, 2019.
    * [17] R. Ganian, F. Klute, and S. Ordyniak.  On structural parameterizations of the bounded-degree vertex deletion problem.  Algorithmica, 83(1):297–336, 2021.
    * [18] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
    * [19] G. Z. Gutin, E. J. Kim, A. Soleimanfallah, S. Szeider, and A. Yeo.  Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming.  Algorithmica, 64(1):112–125, 2012.
    * [20] F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier.  Fixed-parameter algorithms for cluster vertex deletion.  Theory Comput. Syst., 47(1):196–217, 2010.
    * [21] M. Karoński, T. Łuczak, and A. Thomason.  Edge weights and vertex colors.  Journal of Combinatorial Theory, 91:151–157, 05 2004.
    * [22] R. Keusch.  A solution to the 1-2-3 conjecture.  CoRR, abs/2303.02611, 2023.
    * [23] S. Khot and V. Raman.  Parameterized complexity of finding subgraphs with hereditary properties.  Theoretical Computer Science, 289(2):997–1008, 2002.
    * [24] M. Lampis.  Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica, 64(1):19–37, 2012.
    * [25] M. Lampis and M. Vasilakis.  Structural parameterizations for two bounded degree problems revisited.  CoRR, abs/2304.14724, 2023.
    * [26] H. W. Lenstra Jr.  Integer programming with a fixed number of variables.  Mathematics of Operations Research, 8(4):538–548, 1983.
    * [27] J. M. Lewis and M. Yannakakis.  The node-deletion problem for hereditary properties is np-complete.  Journal of Computer and System Sciences, 20(2):219–230, 1980.
    * [28] H. Moser and D. M. Thilikos.  Parameterized complexity of finding regular induced subgraphs.  Journal of Discrete Algorithms, 7(2):181–190, 2009.
    * [29] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer-Verlag Berlin and Heidelberg GmbH $\&$ Co., 2003.