# Correlation Clustering with Vertex Splitting

Matthias Bentert  University of Bergen, Norway<EMAIL_ADDRESS><EMAIL_ADDRESS>Alex Crane  University of Utah, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>Pål Grønås Drange  University of Bergen, Norway.
<EMAIL_ADDRESS><EMAIL_ADDRESS>Felix Reidl  Birkbeck, University
of London, UK<EMAIL_ADDRESS>Blair D. Sullivan  University of Utah, USA.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We explore Cluster Editing and its generalization Correlation Clustering with
a new operation called _permissive vertex splitting_ which addresses finding
overlapping clusters in the face of uncertain information. We determine that
both problems are NP-hard, yet they exhibit significant differences in
parameterized complexity and approximability. For Cluster Editing with
Permissive Vertex Splitting, we show a polynomial kernel when parameterized by
the solution size and develop a polynomial-time algorithm with approximation
factor 7. In the case of Correlation Clustering, we establish para-NP-hardness
when parameterized by solution size and demonstrate that computing an
$n^{1-\varepsilon}$-approximation is NP-hard for any constant $\varepsilon>0$.
Additionally, we extend the established link between Correlation Clustering
and Multicut to the setting with permissive vertex splitting.

##  1 Introduction

Discovering clusters, or communities, is a core task in understanding the vast
amounts of relational data available. One limitation of many traditional
clustering algorithms is the necessity of specifying a desired number of
clusters as part of the input. The Cluster Editing problem avoids this by
instead aiming to minimize the number of edge insertions and removals
necessary to transform the input into a _cluster graph_ (a disjoint union of
cliques). This problem has been heavily studied in the graph algorithms
community, and was first proved to be fixed-parameter tractable with respect
to the number of edge modifications ($k$) by Cai in 1996 [14]. The running
time has significantly improved since, with the best known algorithm running
in $O(1.62^{k}(n+m))$ time [13]. The problem also admits a polynomial kernel
with $2k$ vertices [29].

Formally, in Cluster Editing, we consider a complete graph where each edge is
labeled as positive (which we imagine as colored _blue_) or negative (colored
_red_) and we ask for the minimum number of edges whose color must be changed
so that there is a partition of the vertex set where all edges within each
part are blue, and all edges between parts are red. This convention of an
edge-labeled complete graph will be useful in our setting and easily maps onto
the more common formalism for Cluster Editing with an incomplete, uncolored
graph as input (imagine the graph edges as blue and its non-edges as red). We
also note that other conventions for labelling positive/negative edges exist
in the literature, e.g. using labels like $\langle+\rangle$ and
$\langle-\rangle$.

In practice, the positive or negative association between objects is usually
computed using a similarity metric which we can think of as an oracle function
which, given two objects, computes a score that expresses the (dis)similarity
of the inputs. For large-scale data the assumption of complete information is
then unrealistic for two reasons: First, the quadratic complexity of computing
all pairwise associations is prohibitively expensive. Second, the similarity
oracle may be unable to provide a clear answer for certain pairs—suggesting
that objects can either be grouped together or kept separate, depending on
other parts of the data or even external domain context.

Consequently, we should also consider cases in which the input is an
incomplete graph with positive and negative labels on the existing edges and
no information about pairs not joined by an edge. This scenario has previously
been investigated by Demaine et al. [20] by allowing “$0$-weight edges” (zero-
edges) in their cluster-editing framework111In the version discussed by
Demaine et al. [20], real weights are assigned to edges, reflecting the
certainty level of the oracle in determining the similarity between objects.
We only consider weights $\\{-1,0,1\\}$, a common restriction in the
literature.. For clarity, we will refer to the problem where zero-edges (non-
edges) are allowed as Correlation Clustering and to the problem where the
input graph is _complete_ —i.e. every vertex pair is connected either by a
blue or a red edge—as Cluster Editing.

The approximability of both Cluster Editing and Correlation Clustering are
well-studied. First considered by Bansal, Blum, and Chawla [9], under the name
_correlation clustering_ 222There is significant inconsistency in the
literature regarding the nomenclature of these problems; as stated we reserve
the name Correlation Clustering for the problem where the input is
incomplete., Cluster Editing admits a $2.06$-approximation [17] when
minimizing the number of disagreements (red edges within and blue edges
between clusters). Other variants of Cluster Editing which maximize the number
of agreements or the correlation (agreements minus disagreements) admit a PTAS
(polynomial-time approximation scheme) and a $\Omega(1/\log n)$-approximation,
respectively [9, 15]. In the more general setting of minimizing disagreements
for Correlation Clustering, we must settle for an $O(\log n)$-approximation as
the problem is APX-hard [20]. This result arises from the strong relation
between Correlation Clustering and Multicut333Given a set of pairs of
terminals, $(s_{1},t_{1}),(s_{2},t_{2}),\dots,(s_{p},t_{p})$, find a set of at
most $k$ edges such that after removing these edges, every $s_{i},t_{i}$ pair
is disconnected. The connection was first observed with Multiway Cut by
Bansal, Blum, and Chawla [9], before an approximation-preserving reduction
from Multicut to Correlation Clustering was given independently by both
Charikar, Guruswami, and Wirth [16] and Demaine et al. [20].

These algorithmic advances provide a positive outlook on applying these
clustering variants in practice, however, the underlying assumption that real-
world data segregates into neat, disjoint clusters remains a concern. The
following domain examples illustrate why this assumption is probably too
optimistic:

  * •

Document classification: Individual documents often span multiple topics and
should therefore belong to multiple topic-clusters;

  * •

Sentiment analysis: A single piece of text can express very different emotions
(e.g. sadness mixed with humor);

  * •

Community detection: Individuals typically participate in multiple
communities, such as family, professional, and hobbyist groups; and

  * •

Language processing: Homonyms like “bat” should belong both to an “animal”
cluster as well as a “sports equipment” cluster.

Hence, the emphasis in clustering has recently shifted towards algorithms for
_overlapping clustering_ [1, 5, 6, 7, 8, 11, 12, 18, 19, 22, 25, 26, 27, 28,
31, 32]. These models move away from the requirement that data must be
partitioned into disjoint subsets by considering a variety of definitions for
clusters which may intersect. One natural approach is to edit to a more
general target graph class (instead of a cluster graph, consider minimizing
the number of edge modifications required to achieve some more complex
structure that exhibits strong community structure but allows overlap), but it
is difficult to define generalizations that align with many applications.

Motivated by this, Abu-Khzam et al. [1] proposed a model for overlapping
clustering based on the concept of _splitting_ a vertex into two new vertices,
representing an object having two distinct roles within a dataset. This
approach led to the problem Cluster Editing with Vertex Splitting, where edges
can be added or deleted, and vertices can be split. Here, _splitting_ a vertex
$v$ means replacing it with two copies, $v_{1}$ and $v_{2}$, ensuring the
union of their (blue) neighbor sets equals the original vertex’s (blue)
neighbor set. In fact, Abu-Khzam et al. [1] propose two different vertex
splitting operations: one (_exclusive_ splitting) where $v_{1}$ and $v_{2}$
are required to have disjoint (blue) neighborhoods, and another (_inclusive_
splitting) where they are allowed to share (blue) neighbors. See Figure 1 for
an example. Abu-Khzam et al. [3] show that Cluster Editing with Vertex
Splitting is NP-hard and has a $6k$-vertex kernel, where $k$ is the number of
edits (edge modifications/vertex splits) allowed. The approximability of this
problem remains unknown.

A significant limitation of both existing notions of vertex splitting is that
they require red edges to be preserved by both copies of a split vertex. For
example, consider a red edge $uv$ in data arising from word classification,
where $u$ and $v$ correspond to “bat” and “cat”, respectively. It could be
that the edge was produced by our oracle as a result of “bat” being
interpreted as a piece of sports equipment, not an animal. However, when “bat”
is split so that each meaning has its own vertex, we wish to retain the red
edge only on one of the copies of $v$ (the one _not_ corresponding to the
small flying mammal, as this does have similarities with a cat). Motivated by
this, we introduce a new operation called _permissive vertex splitting_ which
allows replacing a vertex $v$ with two copies $v_{1}$ and $v_{2}$ with the
restriction that if $uv$ is a blue edge (or red edge, respectively), then at
least one of $uv_{1}$ and $uv_{2}$ is a blue edge (red edge, respectively).
Beyond that, we are free to choose what to do with the newly-created
neighborhoods. We call the new problem variant, where edges can be added or
deleted and vertices can be permissively split, Correlation Clustering with
Permissive Vertex Splitting. We show that sequences of permissive vertex
splits solving this problem correspond directly to a natural notion of
overlapping clustering (see Definition 4), adding to the motivation for this
definition of splitting.

Extending the prior work relating Correlation Clustering to Multicut, we show
that Correlation Clustering with Permissive Vertex Splitting can be reduced to
the new problem Multicut with Vertex Splitting (MCVS) and vice versa, meaning
that the computational complexities of these problems are essentially the
same. We then show that Multicut with Vertex Splitting, and hence also
Correlation Clustering with Permissive Vertex Splitting, are para-NP-hard
(with respect to solution size), and NP-hard to approximate within an
$n^{1-\epsilon}$ factor for any $\epsilon>0$. Because of the inherent hardness
of Correlation Clustering with Permissive Vertex Splitting, we then turn our
attention to the setting where there are no zero-edges, i.e., to Cluster
Editing with Permissive Vertex Splitting. We show that this problem remains
NP-hard, but on the positive side admits a polynomial kernel (and thus is
fixed-parameter tractable). Finally, we give a polynomial-time algorithm which
provides a 7-approximation for Cluster Editing with Permissive Vertex
Splitting.

$v_{1}$$v_{2}$$y$$w$$v$$y$$w$$v_{1}$$v_{2}$$y$$w$$v_{1}$$v_{2}$$y$$w$Blue
edgeRed edge Figure 1: A vertex $v$ in an (incomplete) correlation graph
(top). The bottom row gives toy examples of exclusive (left), inclusive
(center), and permissive (right) vertex splits of $v$ into $v_{1}$ and
$v_{2}$. For clarity, some red edges incident to $v_{1}$ and $v_{2}$ are
omitted from each figure on the bottom row.

#### Related Work.

Prior work on overlapping variants of Cluster Editing includes a series of
papers on non-permissive vertex splitting [1, 2, 3, 6], as well as results by
Fellows et al. on the problem where each vertex is restricted to participating
in a fixed number of clusters [24]. The latter problem does not map well to
real data where some entities naturally belong to many clusters, while others
naturally belong to few. Bonchi, Gionis, and Ukkonen [12] have studied
overlapping Correlation Clustering with penalty functions (either the
indicator function or Jaccard) which measure the _extent_ of similarity
between entities’ cluster labels. Our formulation is more permissive, as we
give “full credit” to pairs of similar items as long as some cluster contains
both, and to pairs of dissimilar items as long as they are not each contained
in a single (shared) cluster.

Outside of overlapping clustering, vertex splitting has also found
applications in graph drawing [23, 30, 4] and in the problem of reducing a
graph’s pathwidth [10]. To the best of our knowledge, we are the first to
consider permissive vertex splitting in any setting.

##  2 Preliminaries

We refer the reader to the textbook by Diestel [21] for standard graph-
theoretic definitions and notation. A _star_ is a tree with exactly one
internal vertex. In particular, a star has at least two leaves. For a positive
integer $n$, we denote by $[n]=\\{1,2,\ldots n\\}$ the set of all positive
integers up to $n$. An _incomplete correlation graph_ is a simple, unweighted,
and undirected graph $G=(V,B,R)$ with two disjoint edge relations $B$ (blue)
and $R$ (red). If such a graph is complete, i.e., $R\cup B={V\choose 2}$, then
we call it a _correlation graph_. For a vertex $v\in V$ we write $N^{R}(v)$ to
denote the set of neighbors adjacent to $v$ via red edges (_red neighbors_)
and $N^{B}(v)$ for those adjacent via blue edges (_blue neighbors_). A
_cluster graph_ is a correlation graph in which the blue edges form vertex-
disjoint cliques (and thus all edges between the cliques are red). We can now
formally define our vertex-splitting operation.

######  Definition 1.

A _permissive vertex split_ of a vertex $v$ in an (incomplete) correlation
graph $G$ is the replacement of $v$ in $G$ with two new vertices $v_{1}$ and
$v_{2}$ such that

  * •

$N^{R}(v)\subseteq N^{R}(v_{1})\cup N^{R}(v_{2})$, and

  * •

$N^{B}(v)\subseteq N^{B}(v_{1})\cup N^{B}(v_{2})$,

In other words, we create a new graph where every red (blue) neighbor of $v$
is a red (blue) neighbor of at least one of $v_{1}$ or $v_{2}$. All other
“edges” incident to $v_{1}$ and $v_{2}$ can be chosen arbitrarily. In
particular, in incomplete correlation graphs, we can assume that all these
other edges are neutral (i.e., the “edges” do not exist), while in correlation
graphs, it is usually simpler to make these edges either red or blue to keep
the graph complete. Notably, the edge $v_{1}v_{2}$ can always be assumed to be
a red edge as splitting a vertex into two vertices that end up in the same
(blue) connected component is never advantageous. For the remainder of this
text, unless otherwise specified all vertex splits are permissive. Given a
sequence $\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{k})$ of $k$ vertex
splits performed on an (incomplete) correlation graph we denote the resulting
(incomplete) correlation graph by $G_{|\sigma}$. Each vertex $u$ in
$G_{|\sigma}$ corresponds to exactly one vertex $v$ in $G$. We say that $v$ is
$u$’s _ancestor_ , and that $u$ is a _descendant_ of $v$. If $u=v$, then $u$
and $v$ are _unsplit_ vertices. Otherwise we say that $v$ is a _split_ vertex
and that $u$ is the descendant of a split vertex.

######  Definition 2.

An _erroneous cycle_ is a simple cycle that contains exactly one red edge. An
(incomplete) correlation graph $G$ _contains_ an erroneous cycle if it
contains a subgraph that is an erroneous cycle. A _bad triangle_ is an
erroneous cycle of length 3.

Erroneous cycles are the canonical obstruction in Correlation Clustering [16,
20], and bad triangles are the canonical obstruction in Cluster Editing.
Usually, these problems are formulated as edge editing problems, i.e., delete
a minimum number of edges (blue or red) such that the resulting graph has no
erroneous cycles/bad triangles. Previous work on Cluster Editing with
(inclusive or exclusive) vertex splitting has allowed both edge edits and
vertex splits as editing operations [1, 2, 3, 6]. However, we note that
permissive vertex splitting is flexible enough to capture all editing
operations. In particular, if a red edge $uv$ is deleted, then choose one
endpoint (without loss of generality $v$) and split it into $v_{1}$ and
$v_{2}$ such that $N^{R}(v_{1})=N^{R}(v)\setminus\\{u\\}$,
$N^{B}(v_{1})=N^{B}(v)$, and the red edge $uv_{2}$ is the only edge incident
to $v_{2}$. The result of the edge deletion is now modeled exactly by $v_{1}$,
and the operation is safe because $v_{2}$ cannot participate in any erroneous
cycle, as it only has one edge. Modeling the deletion of a blue edge works
similarly. Moving forward, we assume that all editing operations are vertex
splits, and we say that a sequence $\sigma$ of vertex splits _resolves_ an
(incomplete) correlation graph $G$ if $G_{|\sigma}$ has no erroneous cycles.
We now state the problems that we study:

Input: |  An (incomplete) correlation graph $G$ and a non-negative integer $k$.
---|---
Problem: |  Does there exist a sequence $\sigma$ of at most $k$ vertex splits which resolves $G$?
Correlation Clustering with Permissive Vertex Splitting

Cluster Editing with Permissive Vertex Splitting is the same problem
restricted to correlation graphs. We conclude this section with our main
structural insight, which is that resolving an (incomplete) correlation graph
$G$ via a sequence of vertex splits is equivalent to performing a very natural
notion of overlapping clustering on the vertices of $G$.

######  Definition 3.

A _covering_ of an (incomplete) correlation graph $G=(V,E)$ is a set family
$\mathcal{F}\subseteq 2^{V}$ such that $\bigcup\mathcal{F}=V$. The _cost_ of
the covering $\mathcal{F}$ is

$\operatorname{cost}_{G}(\mathcal{F})=\sum_{v\in V}\\#\mathcal{F}(v)-1,$

where $\\#\mathcal{F}(v):=|\\{X\mid v\in X\in\mathcal{F}\\}|$ counts the
number of sets in $\mathcal{F}$ which contain $v$.

######  Definition 4.

A _overlapping clustering_ of an (incomplete) correlation graph $G$ is a
covering $\mathcal{F}$ with the following two properties:

  * •

for every blue edge $uv\in B$, there exists at least one cluster
$X\in\mathcal{F}$ with $\\{u,v\\}\subseteq X$, and

  * •

for every red edge $uv\in R$, there exists two distinct clusters
$X,Y\in\mathcal{F}$ with $u\in X$ and $v\in Y$.

For a specific edge $uv$, we say that a clustering _covers_ the edge if it is
blue and the first condition holds and we say that it _resolves_ the edge if
it is red and the second condition holds.

######  Lemma 1.

An (incomplete) correlation graph $G$ can be resolved with $k$ vertex splits
if and only if $G$ has an overlapping clustering of cost $k$.

###### Proof.

For the first direction, let $\sigma$ be a sequence of $k$ vertex splits
resolving ${G=(V,B,R)}$, i.e., $\sigma$ produces a graph
$G_{|\sigma}=(V_{|\sigma},E_{|\sigma})$ with no erroneous cycles. We will
construct an overlapping clustering $\mathcal{F}$ of cost at most $k$. We note
that it is easy to extend any such overlapping clustering to one of cost
exactly $k$. We begin by choosing an arbitrary vertex $v\in V_{|\sigma}$. We
denote by $v^{*}$ the ancestor of $v$ in $V$. Let $C_{v}\subseteq V_{|\sigma}$
be the vertices of the connected component of $v$ in the subgraph of
$G_{|\sigma}$ induced by all blue edges, and let $C_{v^{*}}$ be the set of
corresponding ancestor vertices in $V$. We add $C_{v^{*}}$ to $\mathcal{F}$
and remove $C_{v}$ from $G_{|\sigma}$. We repeat this process exhaustively.
The resulting $\mathcal{F}$ is a covering of $G$, as each vertex in $V$ has at
least one descendant in $V_{|\sigma}$. Moreover, our construction guarantees
that each vertex in $V_{|\sigma}$ is considered exactly once. Consequently,
for each vertex $v\in V$ we have that $\\#\mathcal{F}(v)$ is no greater than
the number of descendants of $v$ in $V_{|\sigma}$. Thus, $\mathcal{F}$ has
cost at most $k$. Each blue edge is covered by construction.

For the final step, we show how to augment $\mathcal{F}$ such that all red
edges are resolved while maintaining that
$\operatorname{cost}_{G}(\mathcal{F})\leq k$. We begin by identifying some red
edge $uv$ which is not resolved by $\mathcal{F}$. This implies that each of
$u$ and $v$ are contained in exactly one cluster $X\in\mathcal{F}$. The red
edge $uv$ implies that there is some red edge $u_{1}v_{1}$ in $G_{|\sigma}$,
where $u_{1}$ is a descendant of $u$ and $v_{1}$ is a descendant of $v$.
Moreover, the construction of $\mathcal{F}$ guarantees that there is some blue
path between $v_{1}$ and a descendant of $u$, but this latter descendant
cannot be $u_{1}$ or else we have identified an erroneous cycle in
$G_{|\sigma}$. Thus, $u$ has multiple descendants in $G_{|\sigma}$ and is
therefore a split vertex. Since $u$ is a split vertex but is only contained in
one cluster $X$ in $\mathcal{F}$, we can add the cluster $\\{u\\}$ to
$\mathcal{F}$, thereby resolving $uv$, while maintaining that
$\operatorname{cost}_{G}(\mathcal{F})\leq k$. We repeat this process until all
red edges are resolved.

For the other direction, let $\mathcal{F}$ be an overlapping clustering of $G$
with cost $k$. For each vertex $v$ that is contained in more than one cluster
set in $\mathcal{F}$, we split $v$ a total of ${\\#\mathcal{F}(v)-1}$ times.
We assign each descendant to one set $X\in\mathcal{F}$ with $v\in X$ and we
create blue edges towards all other vertices that are contained in $X$ (or to
the specific descendant of a vertex in $X$ that was also assigned to $X$). All
other edges incident to the descendant of $v$ are red. We first show that this
construction indeed corresponds to a series of vertex splits. For each blue
edge $uv$, we have that there is some cluster set $X\in\mathcal{F}$ with
$u,v\in X$. Hence, if $u$ and/or $v$ are split, then the blue edge $uv$
corresponds to the blue edge between the two descendants of $u$ and $v$ that
are assigned to $X$. For each red edge $uv$, we have that there are some
cluster sets $X\neq Y\in\mathcal{F}$ with $u\in X$ and $v\in Y$. Hence, if $u$
and/or $v$ are split, then the red edge $uv$ corresponds to the red edge
between (the descendant of) $u$ assigned to $X$ and (the descendant of) $v$
that is assigned to $Y$. Moreover, we did exactly
$\operatorname{cost}(\mathcal{F})$ splits.

It remains to show that the sequence of splits results in a graph that
contains no erroneous cycles. Suppose that an erroneous cycle
$(u=v_{0},v_{1},\ldots,v_{p}=w,u)$ with red edge $uw$ remains. Note that each
vertex is assigned to exactly one cluster set in $\mathcal{F}$ as each unsplit
vertex is contained in exactly one set in $\mathcal{F}$ and each descendant of
a split vertex is assigned to a cluster set by construction. We will show that
there is no blue edge between vertices that are assigned to different clusters
and no red edge between vertices that are assigned to the same cluster set.
This finishes the proof as $u$ and $w$ are then assigned to different cluster
sets as they share a red edge, but $v_{i}$ and $v_{i-1}$ are assigned the same
cluster set for each $i\in[p]$, a contradiction. First, assume that there is a
blue edge $xy$ where $x$ and $y$ are assigned to different cluster sets. If
$x$ and $y$ are both unsplit vertices, then the blue edge between them is not
covered by $\mathcal{F}$, a contradiction. Hence, at least one of the two
vertices is the descendant of a split vertex and by construction, all edges to
vertices that are assigned to different cluster sets are red. Now assume that
there is a red edge $xy$ where $x$ and $y$ are assigned to the same cluster
set $X\in\mathcal{F}$. Again, if $x$ and $y$ are both unsplit vertices, then
they are only contained in $X$ in $\mathcal{F}$ and hence the red edge between
them is not resolved by $\mathcal{F}$, a contradiction. So at least one of the
two vertices is the descendant of a split vertex and by construction, all
edges to vertices that are assigned to $X$ are blue, a final contradiction.
This concludes the proof. ∎

##  3 Incomplete Information

We first consider the more general problem, Correlation Clustering with
Permissive Vertex Splitting, which allows for incomplete information. Without
vertex splits, it has long been known that Correlation Clustering is in fact
equivalent to Multicut [20], which is the problem of deleting a minimum number
of edges from a graph $G=(V,E)$ such that every _terminal pair_ of distinct
vertices in a set $S\subseteq V^{2}$ is separated in the resulting graph. We
define Multicut with Vertex Splitting and show that it is equivalent to
Correlation Clustering with Permissive Vertex Splitting. We believe that this
result is of independent interest, but it will also prove immediately useful
as it facilitates the main results of this section. Specifically, Correlation
Clustering with Permissive Vertex Splitting and Multicut with Vertex Splitting
are both para-NP-hard when parameterized by the number of vertex splits, and
it is NP-hard to approximate either problem within a factor of
$n^{1-\varepsilon}$ for any $\varepsilon>0$.

First we must define our new Multicut variant. In this context we use standard
graph terminology, i.e., we discuss simple, unweighted, and undirected graphs
with a single edge relation $E$. Note that this is equivalent to a correlation
graph where edges in $E$ are blue and all other vertex pairs are red, so
permissive vertex splits are still well-defined. However, in the Multicut
context we can safely assume that all vertex splits are _exclusive_ , i.e.,
whenever splitting a vertex $v$ into descendants $v_{1}$ and $v_{2}$ we have
that $N(v_{1})\cup N(v_{2})=N(v)$ and ${N(v_{1})\cap N(v_{2})=\emptyset}$. The
reason is that in Multicut it is never advantageous to assign more edges than
required. Another technical detail to discuss is what happens to a terminal
pair when one of its two vertices is split. We work with the variant where the
terminal pair is simply removed in this case. Note that this is equivalent to
the variant where we can choose either of the descendants to replace the
original vertex in the terminal pair, since as previously mentioned we may
always assume that any two descendants of the same vertex end up in different
connected components.

Input: |  A graph $G=(V,E)$, an integer $k$, and a set $S\subseteq V^{2}$, with $S\cap E=\emptyset$, of _terminal pairs_.
---|---
Problem: |  Does there exist a sequence $\sigma$ of at most $k$ (exclusive) vertex splits such that each pair in $S$ is separated in $G_{|\sigma}$?
Multicut with Vertex Splitting

We now show that Correlation Clustering with Permissive Vertex Splitting and
Multicut with Vertex Splitting are equivalent problems. Let $(G=(V,B,R),k)$ be
an instance of Correlation Clustering with Permissive Vertex Splitting. We
construct an equivalent instance ${(H=(V^{\prime},E^{\prime}),S,k)}$ of
Multicut with Vertex Splitting as follows. For each vertex $v\in V$ we create
a vertex $v^{\prime}$ in $V^{\prime}$. Additionally, for each blue edge $uw\in
B$, we add the edge $u^{\prime}w^{\prime}$ to $E^{\prime}$. Finally, for each
red edge $uw\in R$, we add the terminal pair $(u^{\prime},w^{\prime})$ to $S$.
This completes the construction of $H$.

######  Theorem 1.

For any integer $k\geq 0$, $(G,k)$ is a yes-instance of Correlation Clustering
with Permissive Vertex Splitting if and only if $(H,S,k)$ is a yes-instance of
Multicut with Vertex Splitting.

###### Proof.

For the first direction, let $\sigma=(\sigma_{1},\sigma_{2},\ldots)$ be a
sequence of vertex splits resolving $G$. We will construct a sequence
$\sigma^{\prime}$ of the same length which resolves $H$ by considering each
$\sigma_{i}$ in order. If $\sigma_{i}$ splits vertex $v\in V$ into $v_{1}$ and
$v_{2}$ then $\sigma^{\prime}_{i}$ splits $v^{\prime}$ into $v^{\prime}_{1}$
and $v^{\prime}_{2}$. By construction, each neighbor $u^{\prime}$ of
$v^{\prime}$ corresponds to a blue neighbor $u$ of $v$. If $u$ is a blue
neighbor of $v_{1}$, then we create the edge $v^{\prime}_{1}u^{\prime}$.
Otherwise, we create the edge $v^{\prime}_{2}u^{\prime}$. This completes the
construction of $\sigma^{\prime}$. Now, we assume toward a contradiction that
some terminal pair $(v^{\prime},u^{\prime})$ is connected in
$H_{|\sigma^{\prime}}$. Then there is some path
$(v^{\prime}=w^{\prime}_{0},w_{1},\ldots,w^{\prime}_{p}=u^{\prime})$ in
$H_{|\sigma^{\prime}}$. Note that our construction ensures that this path
contains at least two edges, and that there is a corresponding blue path
$(v=w_{0},w_{1},\ldots,w_{p}=u)$ in $G_{|\sigma}$. Moreover, because
$(v^{\prime},u^{\prime})$ is a terminal pair in $H_{|\sigma^{\prime}}$, $vu$
is a red edge in $G_{|\sigma}$. Thus, we have identified an erroneous cycle
$(v=w_{0},w_{1},\ldots,w_{p}=u,v)$ in $G_{|\sigma}$, contradicting that
$\sigma$ resolves $G$.

For the other direction, let
$\sigma^{\prime}=(\sigma^{\prime}_{1},\sigma^{\prime}_{2},\ldots)$ be a
sequence of vertex splits such that no terminal pair is connected in
$H_{|\sigma^{\prime}}$. As before, we will construct a solution $\sigma$ of
the same length by considering each $\sigma^{\prime}_{i}$ in order. If
$\sigma^{\prime}_{i}$ splits $v^{\prime}$ into $v^{\prime}_{1}$ and
$v^{\prime}_{2}$, then we split the corresponding vertex $v$ into $v_{1}$ and
$v_{2}$ as follows. If $v^{\prime}$ is a terminal with partner $u^{\prime}$,
then our construction guarantees that $vu$ is a red edge in $G$. We create the
red edge $v_{1}u$ if $v^{\prime}_{1}$ (or one of its descendants) is in a
different component from $u$ (or one of its descendants) in
$H_{|\sigma^{\prime}}$. Otherwise, we create the red edge $v_{2}u$. We mark
the relevant pair of descendants so that, when performing subsequent splits,
the red edge is always assigned such that its endpoints in $G_{\sigma}$
correspond to vertices in different connected components of
$H_{|\sigma^{\prime}}$. Next, for each $u^{\prime}\in N(v^{\prime})$, we
create the blue edge $v_{1}u$ if $\sigma^{\prime}_{i}$ assigns $u^{\prime}$ to
$N(v^{\prime}_{1})$. Otherwise, we create the blue edge $v_{2}u$. We now
assume toward a contradiction that there is an erroneous cycle
$(v=w_{0},w_{1},\ldots,w_{p}=u,v)$ in $G_{|\sigma}$, with $vu$ being the red
edge. The blue path $(v=w_{0},w_{1},\ldots,w_{p}=u)$ guarantees that there is
a path
$(v^{\prime}=w_{0}^{\prime},w^{\prime}_{1},\ldots,w_{p}^{\prime}=u^{\prime})$
from $v^{\prime}$ to $u^{\prime}$ in $H_{|\sigma^{\prime}}$, and this together
with the red edge $vu$ implies that $(v^{\prime},u^{\prime})$ is a terminal
pair. This contradicts that no terminal pair is connected in
$H_{|\sigma^{\prime}}.$ ∎

To reduce Multicut with Vertex Splitting to Correlation Clustering with
Permissive Vertex Splitting, we simply reverse the previous reduction of
Correlation Clustering with Permissive Vertex Splitting to Multicut with
Vertex Splitting. Formally, let $(G=(V,E),S,k)$ be an instance of Multicut
with Vertex Splitting. We create an instance $(H=(V^{\prime},B,R),k)$ of
Correlation Clustering with Permissive Vertex Splitting as follows. For each
vertex $v\in V$ we add vertex $v^{\prime}$ to $V^{\prime}$, for each edge
$uw\in E$ we add the blue edge $u^{\prime}w^{\prime}$ to $B$, and finally for
each terminal pair $(u,v)\in S$, we add the red edge $u^{\prime}v^{\prime}$ to
$R$. Note that $B$ and $R$ are disjoint, as by definition no terminal pair in
$S$ is also an edge in $E$.

######  Theorem 2.

For any integer $k\geq 0$, $(G,S,k)$ is a yes-instance of Multicut with Vertex
Splitting if and only if $(H,k)$ is a yes-instance of Correlation Clustering
with Permissive Vertex Splitting.

###### Proof.

Note that applying the reduction behind Theorem 1 to $H$ results in the
instance $(G,S,k)$. Thus, Theorem 1 already shows that the two instances are
equivalent. ∎

Theorems 1 and 2, together with the observation that both reductions exactly
preserve the number of vertices, allow us to state the following strong notion
of equivalence between Correlation Clustering with Permissive Vertex Splitting
and Multicut with Vertex Splitting.

######  Corollary 1.

For any function $f$, Correlation Clustering with Permissive Vertex Splitting
admits a kernel of size $f(k)$ if and only if Multicut with Vertex Splitting
does. Furthermore, the minimization variant of Correlation Clustering with
Permissive Vertex Splitting admits a polynomial-time $f(n)$-approximation
algorithm if and only if the minimization variant of Multicut with Vertex
Splitting does.

Now that we have established the equivalence of Multicut with Vertex Splitting
and Correlation Clustering with Permissive Vertex Splitting, we are ready to
show the hardness of both problems.

######  Theorem 3.

Multicut with Vertex Splitting parameterized by the number of vertex splits is
para-NP-hard. Additionally, for any $\varepsilon>0$ it is NP-hard to
approximate Multicut with Vertex Splitting to within a $n^{1-\varepsilon}$
factor.

###### Proof.

Let $G=(V,E)$ be the input graph for $k$-Colorability with $k\geq 3$. We will
construct an equivalent input instance $(H,S,k-1)$ for Multicut with Vertex
Splitting to establish para-NP-hardness. We construct the graph $H$ and
terminal set $S$ from $G$ as follows. We add $V$ to $H$ and for each edge
$uv\in E$, we add $(u,v)$ to $S$. We then add a new vertex $a$ to $H$, and
create edges from $a$ to all other vertices. This completes the construction.

We first argue that we may assume that any solution of $(H,S,k-1)$ _only_
splits $a$. To see this, let $\sigma$ be a sequence of vertex splits of length
at most $k-1$ such that all terminal pairs are disconnected in $H_{|\sigma}$.
Suppose that some vertex $v\neq a$ is split. Before this split, $v$ only has
one neighbor $a^{*}$, which is either equal to $a$ or a descendant of $a$. We
simply replace the split of $v$ with a split of $a^{*}$ into $a^{*}_{1}$ and
$a^{*}_{2}$ such that $N(a^{*}_{1})=\\{v\\}$ and
$N(a^{*}_{2})=N(a^{*})\setminus\\{v\\}$. In the resulting graph, $v$ is
disconnected from all other vertices in $V$, and so it is disconnected from
all of its terminal partners. We proceed with the assumption that in any
solution $a$ is the only split vertex.

Assume that $(H,S,k-1)$ is a yes-instance. We show that then $G$ is
$k$-colorable. By the above, $H_{|\sigma}$ contains $k$ descendants
$a_{1},\ldots,a_{k}$ of $a$ and these vertices naturally partition the set $V$
into $k$ sets $C_{i}=N(a_{i})$ for $i\in[k]$. No terminal-pair can appear with
both endpoints in one of these sets so the same holds for $E\subseteq S$.
Hence, $C_{1},\ldots,C_{k}$ is a valid $k$-coloring of $G$.

In the other direction, assume that $G$ has a $k$-coloring with the color
partition $C_{1},\ldots,C_{k}$. Then we can split $a\in H$ a total of $k-1$
times into descendants $a_{1},\ldots,a_{k}$ such that $N(a_{i})=C_{i}$. Since
$\\{a_{1},\ldots,a_{k}\\}$ is independent it is easy to verify that these
$k-1$ splits separate every terminal pair in $S$.

We conclude that Multicut with Vertex Splitting is already NP-hard with
parameter $k=2$ as the above provides a reduction from $3$-Colorability. The
approximation hardness follows directly from the facts that, given any
constant $\varepsilon>0$, computing a $n^{1-\varepsilon}$-approximation for
Chromatic Number is NP-hard [33], and that our constructed instance of
Multicut with Vertex Splitting has only $n+1$ vertices. ∎

Taken together with Corollary 1, Theorem 3 gives us the same result for
Correlation Clustering with Permissive Vertex Splitting.

######  Corollary 2.

Correlation Clustering with Permissive Vertex Splitting parameterized by the
number of vertex splits is para-NP-hard. Additionally, for any $\varepsilon>0$
it is NP-hard to approximate Correlation Clustering with Permissive Vertex
Splitting to within a $n^{1-\varepsilon}$ factor.

##  4 Complete Information

We now restrict our study to correlation graphs, i.e., we study Cluster
Editing with Permissive Vertex Splitting. Our main results are NP-hardness
(Section 4.1), a polynomial kernel (Section 4.2), and a polynomial-time
7-approximation (Section 4.3). We begin by introducing a new structure and
subsequent lemmas which will be helpful in attaining the latter two results.

######  Definition 5.

A _bad star_ $S$ in a correlation graph $G$ is a star induced by blue edges.
In particular, the leaves of the star form a red clique in $G$. The _weight_
of a bad star $\operatorname{weight}(S)$ is the number of leaves in the star
minus one. A _bad star forest_ is a collection of vertex-disjoint bad stars
$T$. We write $\operatorname{weight}(T):=\sum_{S\in
T}\operatorname{weight}(S)$ to denote the sum of weights of its members. A
correlation graph $G$ _contains_ a bad star forest if it contains a subgraph
which is a bad star forest.

The first lemma states a useful lower bound in terms of bad stars.

######  Lemma 2.

If $G$ contains a bad star forest of weight $k$ then we need at least $k$
vertex splits to resolve $G$.

###### Proof.

We begin by showing that if $G=(V,B,R)$ contains a subgraph
$H=(V_{H},B_{H},R_{H})$ and at least $k$ vertex splits are needed to resolve
$H$, then at least $k$ vertex splits are needed to resolve $G$. Suppose
otherwise. Then there is some overlapping clustering $\mathcal{F}$ of $G$ with
cost less than $k$. We will construct an overlapping clustering
$\mathcal{F}_{H}$ of $H$ with cost less than $k$. We begin by setting
$\mathcal{F}_{H}=\\{X\cap V_{H}\ |\ X\in\mathcal{F}\\}$. It is clear that this
is a covering of $H$, that every blue edge is covered, and that
$\\#\mathcal{F}_{H}(v)\leq\\#\mathcal{F}(v)$ for every vertex $v\in V_{H}$. We
now ensure that each red edge is resolved. Let $uv$ be a red edge which is not
resolved, meaning that each of $u$ and $v$ belong to only a single cluster
$X\in\mathcal{F}_{H}$. In this case we claim that $\mathcal{F}$ contains two
distinct clusters $Y\neq Z$ such that $Y\cap V_{H}=Z\cap V_{H}=X$. Otherwise,
either $\mathcal{F}$ does not resolve $uv$ or one of $u$ or $v$ is contained
in multiple clusters of $\mathcal{F}_{H}$, both contradictions. Thus, we can
safely add the cluster $\\{u\\}$ (chosen without loss of generality) to
$\mathcal{F}_{H}$, thereby resolving $uv$ while maintaining that
$\\#\mathcal{F}_{H}(u)\leq\\#\mathcal{F}(u)$. We repeat this process
iteratively until we have resolved all red edges. In doing so, we produce an
overlapping clustering $\mathcal{F}_{H}$ of $H$ with
cost${}_{H}(\mathcal{F}_{H})\leq$ cost${}_{G}(\mathcal{F})<k$, a
contradiction.

It remains to show that a bad star forest of weight $k$ requires at least $k$
vertex splits to resolve. We begin by showing that a bad star $S$ of weight
$k$ requires at least $k$ vertex splits. Let $x$ be the center vertex of $S$
and let $\mathcal{F}$ be an overlapping clustering of $S$. Let the clusters in
$\mathcal{F}$ which contain $x$ be ${C_{1},C_{2},\ldots,C_{p}}$. Moreover for
each $1\leq i\leq p$, let $\hat{C}_{i}=C_{i}\setminus\\{x\\}$. Note that we
may assume each $\hat{C}_{i}$ is nonempty, as the cluster $\\{x\\}$ covers no
blue edges and resolves no red edges in $S$, and can therefore be safely
removed from $\mathcal{F}$. Observe also that each leaf $v$ of $S$ must be
contained in some set $\hat{C}_{i}$ since the edge $xv$ is blue. Now suppose
that some leaf $v$ is contained in two sets $\hat{C}_{i}\neq\hat{C}_{j}$. We
remove $v$ from the cluster $C_{j}$ (chosen arbitrarily) and add the cluster
$\\{v\\}$ to $\mathcal{F}$. The blue edge $xv$ is still covered by $C_{i}$,
the cluster $\\{v\\}$ ensures that all red edges incident to $v$ are still
resolved, and we have not increased the cost of the clustering. Thus, we may
safely assume that the sets $\hat{C}_{1},\hat{C}_{2},\ldots\hat{C}_{p}$ are a
partition of the leaves of $S$. Consider one such set $\hat{C}_{i}$. These
leaves induce a red clique and none of these red edges is resolved by $C_{i}$,
so we have that at least $|\hat{C_{i}}|-1$ of these leaves are contained in
multiple clusters in $\mathcal{F}$. Since we also know that
$\\#\mathcal{F}(x)=p$, we conclude

$\displaystyle\operatorname{cost}_{S}(\mathcal{F})$
$\displaystyle\geq(|\hat{C}_{1}|-1)+(|\hat{C}_{2}|-1)+\ldots+(|\hat{C_{p}}|-1)+\\#\mathcal{F}(x)-1$
$\displaystyle=|\hat{C}_{1}|+|\hat{C}_{2}|+\cdots+|\hat{C}_{p}|-p+p-1=|S\setminus\\{x\\}|-1=\operatorname{weight}(S)=k$

Finally, let $T$ be a bad star forest made up of $t$ bad stars
$S_{1},S_{2},\ldots,S_{t}$. Let $k$ be the weight of $T$ and suppose toward a
contradiction that $T$ admits an overlapping clustering $\mathcal{F}$ of cost
less than $k$. Then, we repeat the technique from earlier in this proof to
construct overlapping clusterings
$\mathcal{F}_{S_{1}},\mathcal{F}_{S_{2}},\ldots\mathcal{F}_{S_{t}}$ of the bad
stars. Because the bad stars are vertex-disjoint, we have that
$\text{cost}_{S_{1}}(\mathcal{F}_{S_{1}})+\text{cost}_{S_{2}}(\mathcal{F}_{S_{2}})+\ldots+\text{cost}_{S_{t}}(\mathcal{F}_{S_{t}})\leq\text{cost}_{T}(\mathcal{F})<k$.
This implies that there is some $S_{i}$ such that
$\text{cost}_{S_{i}}(\mathcal{F}_{S_{i}})$ is less than the weight of $S_{i}$,
but we have already proven that this is impossible. ∎

The second lemma states that every optimal solution contains a cluster that
contains all vertices of a sufficiently large blue clique.

######  Lemma 3.

If a correlation graph $G$ contains a blue clique $C$ of size at least $k+1$,
then any overlapping clustering $\mathcal{F}$ of cost at most $k$ contains a
set $X\in\mathcal{F}$ with $C\subseteq X$.

###### Proof.

Let $C$ be blue clique in $G$ of size at least $k+1$ and let $\mathcal{F}$ be
any overlapping clustering of cost at most $k$. Assume towards a contradiction
that $\mathcal{F}$ does not contain a set $X$ with $C\subseteq X$. Since
$\mathcal{F}$ has cost at most $k$, there exists a vertex $v\in C$ that is
contained in exactly one set $Y\in\mathcal{F}$. Moreover, since $Y$ does not
contain all vertices of $C$ by assumption, there exists a vertex $u\in
C\setminus Y$. Since $C$ is a blue clique, the edge $uv$ is blue and is
covered by some set $Z\in\mathcal{F}$. Observe that $Y\neq Z$ as $u\in Z$ and
$u\notin Y$. Since $Z$ covers the edge $uv$, it holds that $v\in Z$, a
contradiction to the assumption that $v$ is only contained in $Y$. ∎

###  4.1 NP-hardness

We now show that Cluster Editing with Permissive Vertex Splitting is NP-hard.

######  Proposition 1.

Deciding whether a given correlation graph admits an overlapping clustering of
cost at most $k$ is NP-hard.

###### Proof.

We reduce from Vertex Cover. Let $(G=(V,E),k^{\prime})$ be an instance of
Vertex Cover. We construct a correlation graph $H$ as follows. Let $U$ be a
set of $k^{\prime}+1$ vertices (not contained in $V$). The vertex set of $H$
is $U\cup V$. For each edge $e=uv\in E$, we add a red edge $uv$ to $H$. All
other edges (including all edges incident to a vertex in $U$) are blue.
Finally, we set $k=k^{\prime}$.

We next show that the reduction is correct. First assume that there is an
overlapping clustering $\mathcal{F}$ of $H$ of cost at most $k$. By Lemma 3,
for each vertex ${v\in V}$, there exists a set $X_{v}\in\mathcal{F}$ with
$U\cup\\{v\\}\subseteq X_{v}$. Note that $U\subset X_{u}\cap X_{v}$ for any
pair $u,v\in V$ and therefore $X_{u}=X_{v}$ as otherwise the cost of
$\mathcal{F}$ is at least $|U|>k$. Hence, there exists a set $X\in\mathcal{F}$
with $U\cup V\subseteq X$. Since all blue edges are covered by $X$, we next
focus on resolving all red edges. Note that since $X$ contains all vertices in
$H$ and the cost of $\mathcal{F}$ is at most $k$, all remaining sets in
$\mathcal{F}^{\prime}=\mathcal{F}\setminus X$ contain at most $k$ vertices
combined. If for some red edge $uv$ none of the two vertices $u$ or $v$ is
contained in a set in $\mathcal{F}^{\prime}$, then this red edge is not
resolved by $\mathcal{F}$. Thus for each red edge, at least one of the two
endpoints is contained in a set in $\mathcal{F}^{\prime}$. Note that this
immediately implies that $G$ contains a vertex cover of size at most $k$ (all
vertices that are contained in a set in $\mathcal{F}^{\prime}$).

For the other direction, assume that $G$ contains a vertex cover $S$ of size
at most $k$. We construct an overlapping clustering $\mathcal{F}$ of $H$ of
cost at most $k$ as follows. The family $\mathcal{F}$ contains one set
$X=U\cup V$ and for each vertex $v\in S$, it contains a set $X_{v}=\\{v\\}$.
Note that the cost of $\mathcal{F}$ is at most $k$ and all blue edges in $H$
are covered by $X$. Moreover, each red edge $uw$ in $H$ is resolved as by
construction it holds that $\mathcal{F}$ contains the set $X_{u}=\\{u\\}$ or
$X_{w}=\\{w\\}$. Without loss of generality, let $\mathcal{F}$ contain
$X_{u}$. Then, the red edge $uw$ is resolved as $w$ is contained in $X$ and
$u$ is contained in $X_{u}\neq X$. This concludes the proof. ∎

###  4.2 Polynomial Kernel

We next show that Cluster Editing with Permissive Vertex Splitting
parameterized by $k$ admits a polynomial kernel. Note that this is in stark
contrast to the para-NP-hardness of Correlation Clustering with Permissive
Vertex Splitting when paramterized by $k$.

######  Theorem 4.

Cluster Editing with Permissive Vertex Splitting parameterized by the number
of vertex splits admits a kernel with $O(k^{3})$ vertices.

###### Proof.

Let $(G=(V,B,R),k)$ be the input instance of Cluster Editing with Permissive
Vertex Splitting. We begin by computing an inclusion-maximal bad star forest
$T$ in $G$. If $\operatorname{weight}(T)\geq k$, then we conclude, according
to Lemma 2, that $(G,k)$ is a no-instance and output an appropriate trivial
kernel.

Otherwise let $S$ be the vertices of $T$ and note that $|S|\leq
3\operatorname{weight}(T)\leq 3k$. Since $T$ is inclusion-maximal, we know
that $G\setminus S$ cannot contain any bad stars and in particular no bad
triangles. We conclude that $G\setminus S$ is therefore a cluster graph. Let
$C_{1},C_{2},\ldots,C_{p}$ be these clusters. We next exhaustively apply the
following simple reduction rule.

######  Reduction rule 1.

If $G$ contains a blue clique $C$ such that all edges with one endpoint in $C$
are red, then remove $C$ from $G$.

Next, we bound the number $p$ of cliques in $G\setminus S$ as follows. Assume
that $G\setminus S$ contains at least $4k+1$ cliques. Note that by application
of Reduction Rule 1, all clusters in $G\setminus S$ have at least one blue
edge towards $S$. Pick for each clique $C$ in $G\setminus S$ one such blue
edge towards $S$ and let $v_{C}$ be the endpoint in $C$ of this edge. Note
that these chosen edges form a collection of vertex-disjoint stars with all
centers in $S$ (but not necessarily all vertices in $S$ being centers).
Moreover, since the vertices $v_{C}$ and $v_{C^{\prime}}$ belong to different
cliques for each pair $C\neq C^{\prime}$ of cliques in $G\setminus S$, the
edge between the two is red. Hence, all stars with at least two leaves in
$V\setminus S$ are bad stars. Let $S^{\prime}\subseteq S$ be the set of
vertices in $S$ that are not the center of such bad stars, that is, vertices
in $S$ for which we chose at most one incident blue edge as a representative
for a clique. Let $S^{*}=S\setminus S^{\prime}$. Since we chose at most one
blue edge $sv_{C}$ for each vertex $s\in S^{\prime}$, the number of chosen
blue edges included in bad stars is at least

$(4k+1)-|S^{\prime}|\geq(4k+1)-|S|+|S^{*}|\geq(4k+1)-3k+|S^{*}|=k+1+|S^{*}|.$

Hence, the weight of the constructed collection of bad stars is at least $k+1$
and by Lemma 2, we conclude that $(G,k)$ is a no-instance. Thus, if
$G\setminus S$ contains at least ${4k+1}$ cliques after applying Reduction
Rule 1 exhaustively, we can return a trivial no-instance. Otherwise, the
number $p$ of cliques is bounded by $4k$.

We are now left with the task of bounding the size of each individual cluster
$C_{i}$ to arrive at a polynomial kernel. To that end, we apply the following
marking and deletion procedure to each cluster: For a fixed cluster $C_{i}$,
begin with an initially empty set $M_{i}$. For each vertex $v\in S$,
arbitrarily mark $k+1$ red and $k+1$ blue neighbors of $v$ in $C_{i}$ by
adding them to $M_{i}$ (or all red/blue neighbors if there are at most $k$).
Note that we mark at most $|M_{i}|\leq|S|(2k+2)\leq 6k^{2}+6k$ vertices this
way.

######  Reduction rule 2.

For any cluster $C_{i}$, delete all (unmarked) vertices in $C_{i}\setminus
M_{i}$ from $G$.

Let $\hat{G}$ be the graph obtained after applying the reduction rule to some
cluster $C_{i}$. We now need to show that this reduction rule is safe and
sound. Let $R_{i}:=C_{i}\setminus M_{i}$ be the vertices removed by the
reduction rule.

First note that if $\mathcal{F}$ is an overlapping clustering of $G$, then
$\mathcal{F}\setminus R_{i}$ (interpreted as a multiset444Technically an
overlapping clustering cannot be a multiset. We refer the reader to the proof
of Lemma 2, in which we formally show how to adapt this construction into an
overlapping clustering with cost bounded by
$\operatorname{cost}_{G}(\mathcal{F})$., that is, the same cluster might
appear multiple times in it) is trivially an overlapping clustering of
$\hat{G}$ and

$\operatorname{cost}_{\hat{G}}(\mathcal{F}\setminus
R_{i})\leq\operatorname{cost}_{G}(\mathcal{F}).$

Thus, the reduction rule is safe.

To prove soundness, let $\hat{\mathcal{F}}$ be an overlapping clustering of
$\hat{G}$ with $\operatorname{cost}_{\hat{G}}(\hat{\mathcal{F}})\leq k$. Let
$u\in R_{i}$ be one of the removed vertices. We argue that we can include $u$
in the clustering without increasing the cost. Note that since we removed a
vertex, the size of $C_{i}$ was initially at least $2k+2$ and hence, by Lemma
3, we have that $\hat{\mathcal{F}}$ contains a set $\hat{C}$ with
$C_{i}\subseteq\hat{C}$. We add $u$ to this cluster and now argue that $u$
does not have to be included in any further clusters if $(G,k)$ is a yes-
instance. To that end, we show that every edge incident to $u$ is already
covered/resolved by this new clustering.

Let $uv$ be any blue edge incident to $u$. Note that if $v\in C_{i}$ then $uv$
is covered by $\hat{C}$, so we may assume that $v\in S$. Then $v$ has at least
$k+2$ blue neighbors in $C_{i}$ as otherwise we would have marked $u$. Let $N$
be a set of $k+1$ neighbors of $v$ in $C_{i}$ that were marked. By Lemma 3,
there exists a cluster set $X\in\hat{\mathcal{F}}$ with $N\cup\\{v\\}\subseteq
X$. Hence, $X=\hat{C}$ as otherwise the cost of $\hat{\mathcal{F}}$ would be
at least $k+1$ as each vertex in $N$ would appear in at least two sets. Thus,
$uv$ is covered by $\hat{C}\cup\\{u\\}$ in the constructed overlapping
clustering.

Now let $uv$ be any red edge incident to $u$. Again, we claim that because $u$
was unmarked, $v$ must have at least $k+2$ red neighbors in $C_{i}$. Either
$v\in S$, in which case the argument is the same as before, or $v\in
V\setminus(S\cup C_{i})$. In this case, all of $C_{i}$ is contained in $v$’s
red neighborhood, and we have already observed that $C_{i}$ has at least
$2k+2$ vertices. Let $N$ be a set of $k+1$ red neighbors of $v$ in $C_{i}$
that were marked. Note that $v$ is contained in a set
$X\neq\hat{C}\in\hat{\mathcal{F}}$ as otherwise each vertex in $N$ would be
contained in at least two sets and $\operatorname{cost}(\hat{\mathcal{F}})\geq
k+1$. Hence, $uv$ is resolved as $u\in\hat{\mathcal{C}}\cup\\{u\\}$ and $v\in
X$.

We conclude that the resulting clustering covers all blue edges incident to
$u$ and resolves all red edges incident to $u$ at the same cost as the
clustering $\hat{\mathcal{F}}$. By repeating the procedure for the remaining
vertices of $R_{i}$ we conclude that there exists a clustering $\mathcal{F}$
which resolves $G$ and
$\operatorname{cost}_{G}(\mathcal{F})=\operatorname{cost}_{\hat{G}}(\hat{\mathcal{F}})$.
Repeating this argument for every cluster demonstrates that Rule 2 is indeed
sound.

Finally, note that after application of Rule 1 and Rule 2 to a yes-instance,
we have $p\leq 4k$ clusters of size at most $|S|2(k+1)\leq 6k^{2}+6k$ each and
therefore the total number of vertices in the end is at most

$|S|+4k(6k^{2}+6k)=24k^{3}+24k^{2}+3k\in O(k^{3}).$

This concludes the proof. ∎

###  4.3 Constant-Factor Approximation

We conclude this section with a constant-factor approximation for Cluster
Editing with Permissive Vertex Splitting. Again, this is in stark contrast to
Correlation Clustering with Permissive Vertex Splitting.

######  Theorem 5.

Cluster Editing with Permissive Vertex Splitting admits a 7-approximation in
polynomial time.

###### Proof.

Let $G=(V,E)$ be a correlation graph. We again begin by computing an
inclusion-maximal bad star forest $T$ in $G$. By Lemma 2, the weight of $T$ is
at most $\operatorname{opt}$ (the minimum cost of an overlapping clustering of
$G$). Since the number of vertices in a bad star is at most thrice its weight
(a bad triangle has weight one and contains three vertices), the set $S$ of
vertices in $T$ is at most $3\operatorname{opt}$. Since $T$ is inclusion-
maximal, the graph induced by $V\setminus S$ does not contain any bad star,
that is, the blue edges form a cluster graph. Let $\mathcal{C}$ be the set of
(blue) cliques in this graph. If $|\mathcal{C}|\leq 1$, then we find a simple
3-approximation by putting each vertex $v\in S$ into its own cluster set
$X_{v}$ and adding one cluster set $X_{S}=V$. Note that the cost of this
overlapping clustering is $|S|\leq 3\operatorname{opt}$. Hence, we assume for
the remainder of the proof that $|\mathcal{C}|\geq 2$.

Next, we restrict our search to a solution that contains one cluster set
$X_{S}$ with $S\subseteq X_{S}$ and for each vertex $v\in S$ one cluster set
$X_{v}=\\{v\\}$. Note that we can add these sets to any solution (if they are
not already present within the solution) to get a new solution whose cost is
at most $2|S|\leq 6\operatorname{opt}$ larger than the original. We call
overlapping clusterings that satisfy the above _simple solutions_ and we
denote the minimum cost of a simple solution by $\operatorname{opt}^{\prime}$.

We next show that there is always a simple solution of cost
$\operatorname{opt}^{\prime}$ that contains for each clique $C\in\mathcal{C}$
a cluster set $X_{C}$ with $C\subseteq X_{C}$. Start with any simple solution
$\mathcal{F}$ of cost $\operatorname{opt}^{\prime}$ and any clique
$C\in\mathcal{C}$ and assume that $\mathcal{F}$ does not contain a cluster set
containing $C$. We prove that in this case each vertex in $C$ is contained in
at least two cluster sets in $\mathcal{F}$. Assume towards a contradiction
that some vertex $v\in C$ is contained in exactly one cluster set $Y$ (note
that by definition of overlapping clusterings, each vertex is contained in at
least one cluster set). Since we assumed that no cluster set completely
contains $C$, there exists a vertex $u\in C\setminus Y$. However, since $u$
and $v$ are contained in the same clique $C$, the edge between them is blue
and has to be covered by some cluster set $Z\in\mathcal{F}$ (and hence $Z$ has
to contain both $u$ and $v$). Note that $Z\neq Y$ since $u\in Z$ but $u\notin
Y$. This contradicts the assumption that $v$ is only contained in cluster set
$Y$.

We construct a new simple solution $\mathcal{F}^{\prime}$ of cost
$\operatorname{opt}^{\prime}$ by removing all vertices in $C$ from all cluster
sets in $\mathcal{F}$ and adding them all to $X_{S}$. In addition, we add one
new cluster set $X_{C}=C$. Note that the cost of $\mathcal{F}^{\prime}$ is at
most the cost of $\mathcal{F}$ as we removed each vertex in $C$ from at least
two cluster sets and added them to exactly two cluster sets. Moreover, the new
solution is indeed an overlapping clustering as all blue edges incident to a
vertex in $C$ are covered by $X_{S}$ as all blue neighbors are either in $S$
or in $C$. Since no red neighbors of any vertex in $C$ are contained in $C$,
the new cluster set $X_{C}$ ensures that all red edges incident to vertices in
$C$ are resolved. Repeating the above for all cliques in $\mathcal{C}$ yields
a simple solution of cost $\operatorname{opt}^{\prime}$ that contains for each
clique $C\in\mathcal{C}$ a cluster set $X_{C}$ with $C\subseteq X_{C}$.

The next step is to show that there is always an optimal simple solution (a
simple solution of cost $\operatorname{opt}^{\prime}$) in which $X_{C}\neq
X_{C^{\prime}}$ for any pair $C\neq C^{\prime}\in\mathcal{C}$. Start with any
optimal simple solution $\mathcal{F}$ that contains a cluster set
$X_{C}\supseteq C$ for each clique $C\in\mathcal{C}$ and assume that
$X_{C_{1}}=X_{C_{2}}$ for some cliques $C_{1}\neq C_{2}$. Observe that all
vertices from at least one of the two cliques are contained in at least two
cluster sets each as if there are vertices $u\in C_{1}$ and $v\in C_{2}$ that
are only contained in $X_{C_{1}}=X_{C_{2}}$, then the red edge between them is
not resolved by $\mathcal{F}$. Without loss of generality, let all vertices of
$C_{1}$ be contained in at least two cluster sets each. Then, we construct a
new simple solution $\mathcal{F}^{\prime}$ of cost
$\operatorname{opt}^{\prime}$ by removing all vertices in $C_{1}$ from all
cluster sets in $\mathcal{F}$ and adding them all to $X_{S}$ and adding one
new cluster set $X_{C_{1}}=C_{1}$. The proof that this is correct is exactly
the same as before. The cost of $\mathcal{F}^{\prime}$ is at most the cost of
$\mathcal{F}$ as we removed each vertex in $C_{1}$ from at least two cluster
sets and added them to exactly two cluster sets. Moreover, the new solution is
indeed an overlapping clustering as all blue edges incident to a vertex in
$C_{1}$ are covered by $X_{S}$ and the new cluster set $X_{C_{1}}$ ensures
that all red edges incident to vertices in $C$ are resolved. Repeating the
above for all cliques in $\mathcal{C}$ yields an optimal simple solution that
contains for each clique $C\in\mathcal{C}$ a cluster set $X_{C}\supseteq C$
such that $X_{C}\neq X_{C^{\prime}}$ for all $C\neq C^{\prime}\in\mathcal{C}$.

Next, we guess which clique $C^{*}\in\mathcal{C}$ satisfies $X_{C^{*}}=X_{S}$
in an optimal simple solution satisfying all of the above.555We can assume
that one such clique always exists, but even if this was not the case, the
following proof still works if the guess $\\{C^{*}\\}=\emptyset$ yields an
optimal simple solution. By that, we mean that we try all possibilities of the
following and return the best solution found. For each clique
$C\in\mathcal{C}\setminus\\{C^{*}\\}$, we compute a minimum vertex cover
$K_{C}$ of the blue edges between $C$ and $S$ in $O(n^{3})$ time using Kőnig’s
theorem (note that the considered graph is bipartite by construction). We add
each vertex in $K_{C}\cap S$ to $X_{C}$ and each vertex in $K_{C}\cap C$ to
$X_{S}$.

We claim that
$\sum_{C\in\mathcal{C}\setminus\\{C^{*}\\}}|K_{C}|\leq\operatorname{opt}^{\prime}-|S|$.
By the above arguments, we can start with an overlapping clustering
$\mathcal{F}$ consisting of one cluster set $X_{S}=S\cup C^{*}$, one cluster
set $X_{C}=C$ for each $C\in\mathcal{C}\setminus\\{C^{*}\\}$, and one cluster
set $X_{v}=\\{v\\}$ for each $v\in S$. Note that all red edges are resolved
and all blue edges except for those between $S$ and $V\setminus(S\cup C^{*})$
are covered. To cover a blue edge $uv$ with $u\in S$ and $v\in C$ for some
$C\in\mathcal{C}\setminus\\{C^{*}\\}$, there are three possibilities: We can
add $u$ to $X_{C}$, we can add $v$ to $X_{S}$, or there exists a different
cluster set $Y\in F$ with $\\{u,v\\}\subseteq Y$. Note that in the third case,
we can remove $v$ from $Y$ and add it to $X_{S}$ and still get an optimal
simple solution. Moreover, the optimal way to cover all blue edges between $S$
and $V\setminus(S\cup C^{*})$ using the first two possibilities corresponds
exactly to $\sum_{C\in\mathcal{C}\setminus\\{C^{*}\\}}|K_{C}|$. Since now all
red edges are resolved and all blue edges are covered and the cost of the
constructed overlapping clustering is

$|S|+\sum_{C\in\mathcal{C}\setminus\\{C^{*}\\}}|K_{C}|\leq\operatorname{opt}^{\prime}\leq
7\operatorname{opt},$

we successfully computed a factor-7 approximation in polynomial time. ∎

We leave it as an open problem to improve the approximation factor. We
conjecture that a refined concept of a simple solution might yield an
approximation factor of $4$.

##  5 Conclusion

We have introduced permissive vertex splitting, which generalizes the earlier
exclusive and inclusive vertex splitting notions by allowing symmetry with
respect to “positive” and “negative” pairwise similarity data. Our type of
vertex splitting turns out to be quite satisfying, as it corresponds to a
natural definition of overlapping clustering. Unfortunately, the general case
of Correlation Clustering with Permissive Vertex Splitting is rather
intractable, as it is para-NP-hard and admits no $n^{1-\varepsilon}$
approximation in polynomial time for any $\varepsilon>0$ (unless P = NP).

On the positive side, when restricted to datasets with complete data we obtain
a kernel with $O(k^{3})$ vertices and a polynomial time 7-approximation.
Interesting questions remain, for example whether one can reduce our
approximation factor to $4$ (or even lower), whether a kernel with only
linearly many vertices exists (as is the case when only inclusive splits and
edge-edits are allowed [3]), or whether refined lower bounds in terms of
running time or approximation factor can be found. Future work might also
consider the parameterized complexity of Correlation Clustering with
Permissive Vertex Splitting and Cluster Editing with Permissive Vertex
Splitting with respect to structural parameters of the input, or with
restrictions on the number of clusters which contain any given node.

Finally, we would like to amplify the call of Abu-Khzam et al. [3] to extend
the study of vertex splitting (exclusive, inclusive, or permissive) to other
classes of target graphs, many of which (e.g., bicluster graphs, $s$-cliques,
$s$-clubs, $s$-plexes, $k$-cores, and $\gamma$-quasi-cliques) have been
proposed as alternatives to cliques in clustering applications.

##  6 Acknowledgements

This work was funded in part by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No. 819416), and the Gordon & Betty Moore Foundation’s Data Driven
Discovery Initiative (award GBMF4560 to Blair D. Sullivan).

## References

  * Abu-Khzam et al. [2018] F. N. Abu-Khzam, J. Egan, S. Gaspers, A. Shaw, and P. Shaw.  Cluster editing with vertex splitting.  In _Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO ’18)_ , pages 1–13. Springer, 2018.
  * Abu-Khzam et al. [2021] F. N. Abu-Khzam, J. R. Barr, A. Fakhereldine, and P. Shaw.  A greedy heuristic for cluster editing with vertex splitting.  In _Proceedings of the 4th International Conference on Artificial Intelligence for Industries (AI4I ’21)_ , pages 38–41. IEEE, 2021.
  * Abu-Khzam et al. [2023] F. N. Abu-Khzam, E. Arrighi, M. Bentert, P. G. Drange, J. Egan, S. Gaspers, A. Shaw, P. Shaw, B. D. Sullivan, and P. Wolf.  Cluster editing with vertex splitting.  _arXiv preprint arXiv:1901.00156_ , 2023.
  * Ahmed et al. [2022] A. R. Ahmed, S. G. Kobourov, and M. Kryven.  An FPT algorithm for bipartite vertex splitting.  In _Proceedings of the 30th International Symposium on Graph Drawing (GD ’22)_ , pages 261–268. Springer, 2022.
  * Arora et al. [2012] S. Arora, R. Ge, S. Sachdeva, and G. Schoenebeck.  Finding overlapping communities in social networks: Toward a rigorous approach.  In _Proceedings of the 13th ACM Conference on Electronic Commerce (EC ’12)_ , pages 37–54. Association for Computing Machinery, 2012\.
  * Arrighi et al. [2023] E. Arrighi, M. Bentert, P. G. Drange, B. D. Sullivan, and P. Wolf.  Cluster editing with overlapping communities.  In _Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC ’23)_ , pages 2:1–2:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
  * Askeland [2022] G. Askeland.  Overlapping community detection using cluster editing with vertex splitting.  Master’s thesis, University of Bergen, Bergen, Norway, 2022.
  * Bandyopadhyay et al. [2015] S. Bandyopadhyay, G. Chowdhary, and D. Sengupta.  FOCS: Fast overlapped community search.  _IEEE Transactions on Knowledge and Data Engineering_ , 27(11):2974–2985, 2015.
  * Bansal et al. [2004] N. Bansal, A. Blum, and S. Chawla.  Correlation clustering.  _Machine Learning_ , 56(1-3):89–113, 2004.
  * Baumann et al. [2023] J. Baumann, M. Pfretzschner, and I. Rutter.  Parameterized complexity of vertex splitting to pathwidth at most 1.  In _Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’23)_ , pages 30–43. Springer, 2023.
  * Baumes et al. [2005] J. Baumes, M. Goldberg, and M. Magdon-Ismail.  Efficient identification of overlapping communities.  In _Proceedings of the 2005 IEEE International Conference on Intelligednce and Security Informatics (ISI ’05)_ , pages 27–36. Springer, 2005\.
  * Bonchi et al. [2013] F. Bonchi, A. Gionis, and A. Ukkonen.  Overlapping correlation clustering.  _Knowledge and Information Systems_ , 35(1):1–32, 2013.
  * Böcker [2012] S. Böcker.  A golden ratio parameterized algorithm for cluster editing.  _Journal of Discrete Algorithms_ , 16:79–89, 2012.
  * Cai [1996] L. Cai.  Fixed-parameter tractability of graph modification problems for hereditary properties.  _Information Processing Letters_ , 58(4):171–176, 1996.
  * Charikar and Wirth [2004] M. Charikar and A. Wirth.  Maximizing quadratic programs: Extending Grothendieck’s inequality.  In _Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’04)_ , pages 54–60. IEEE, 2004.
  * Charikar et al. [2005] M. Charikar, V. Guruswami, and A. Wirth.  Clustering with qualitative information.  _Journal of Computer and System Sciences_ , 71(3):360–383, 2005.
  * Chawla et al. [2015] S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev.  Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs.  In _Proceedings of the 47th Annual ACM symposium on Theory of computing (STOC ’15)_ , pages 219–228. ACM, 2015.
  * Crane et al. [2024] A. Crane, B. Lavallee, B. D. Sullivan, and N. Veldt.  Overlapping and robust edge-colored clustering in hypergraphs.  In _Proceedings of the 17th International Conference on Web Search and Data Mining (WSDM ’24)_. ACM, 2024.
  * Davis and Carley [2008] G. B. Davis and K. M. Carley.  Clearing the FOG: Fuzzy, overlapping groups for social networks.  _Social Networks_ , 30(3):201–212, 2008.
  * Demaine et al. [2006] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica.  Correlation clustering in general weighted graphs.  _Theoretical Computer Science_ , 361(2-3):172–187, 2006.
  * Diestel [2012] R. Diestel.  _Graph Theory_.  Springer, 2012.
  * Du et al. [2008] N. Du, B. Wang, B. Wu, and Y. Wang.  Overlapping community detection in bipartite networks.  In _Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT ’08)_ , pages 176–179, 2008.
  * Eades and de Mendonça Neto [1995] P. Eades and C. F. X. de Mendonça Neto.  Vertex splitting and tension-free layout.  In _Proceedings of the 1995 Symposium on Graph Drawing (GD ’95)_ , pages 202–211. Springer, 1995.
  * Fellows et al. [2011] M. R. Fellows, J. Guo, C. Komusiewicz, R. Niedermeier, and J. Uhlmann.  Graph-based data clustering with overlaps.  _Discrete Optimization_ , 8(1):2–17, 2011.
  * Galbrun et al. [2014] E. Galbrun, A. Gionis, and N. Tatti.  Overlapping community detection in labeled graphs.  _Data Mining and Knowledge Discovery_ , 28(5-6):1586–1610, 2014.
  * Gil-García and Pons-Porrata [2010] R. Gil-García and A. Pons-Porrata.  Dynamic hierarchical algorithms for document clustering.  _Pattern Recognition Letters_ , 31(6):469–477, 2010.
  * Goldberg et al. [2010] M. Goldberg, S. Kelley, M. Magdon-Ismail, K. Mertsalov, and A. Wallace.  Finding overlapping communities in social networks.  In _Proceedings of the 2nd IEEE International Conference on Social Computing (SC ’10)_ , pages 104–113, 2010.
  * Gregory [2007] S. Gregory.  An algorithm to find overlapping community structure in networks.  In _Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD ’07)_ , pages 91–102. Springer, 2007.
  * Guo [2009] J. Guo.  A more effective linear kernelization for cluster editing.  _Theoretical Computer Science_ , 410(8-10):718–726, 2009.
  * Nöllenburg et al. [2022] M. Nöllenburg, M. Sorge, S. Terziadis, A. Villedieu, H. Wu, and J. Wulms.  Planarizing graphs and their drawings by vertex splitting.  In _Proceedings of the 30th International Symposium on Graph Drawing (GD ’22)_ , pages 232–246. Springer, 2022.
  * Wang and Fleury [2010] Q. Wang and E. Fleury.  Uncovering overlapping community structure.  In _Proceedings of the 2nd International Workshop on Complex Networks (COMPLEX ’10)_ , pages 176–186. Springer, 2010.
  * Wang et al. [2010] X. Wang, L. Tang, H. Gao, and H. Liu.  Discovering overlapping groups in social media.  In _Proceedings of the 2010 IEEE International Conference on Data Mining (ICDM ’10)_ , pages 569–578, 2010.
  * Zuckerman [2007] D. Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  _Theory of Computing_ , 3(1):103–128, 2007.