Alternating Path and Coloured Clustering
Leizhen CAI On Yin LEUNG

Phonon coherences reveal the polaronic character of excitons in two-dimensional lead-halide perovskites
    Ajay Ram Srimath Kandada
    December 30, 2023
=======================================================================================================




In the Coloured Clustering problem, we wish to colour vertices
of an edge coloured graph to produce as many stable edges as possible, i.e., 
edges with the same colour as their ends.
In this paper, we reveal that the problem is in fact a maximum subgraph
problem concerning monochromatic subgraphs and alternating paths, and 
demonstrate the usefulness of such connection in studying these problems.

We obtain a faster algorithm to solve the problem for edge-bicoloured graphs
by reducing the problem to a minimum cut problem.
On the other hand, we push the NP-completeness of the problem to edge-tricoloured 
planar bipartite graphs of maximum degree four.
Furthermore, we also give FPT algorithms for the problem when we take the numbers 
of stable edges and unstable edges, respectively, as parameters.





§ INTRODUCTION


The following Coloured Clustering problem has been proposed recently by 
Angel et al. <cit.> in connection with the classical correlation 
clustering problem <cit.>: Compute a vertex colouring of 
an edge-coloured graph G to produce as many stable edges
as possible, i.e., edges with the same colour as their ends.
As observed by Ageev and Kononov <cit.>, the problem contains
the classical maximum matching problem as a special case as the two problems
coincide when all edges have different colours in G.

In this paper we will reveal that Coloured Clustering, despite its 
definition by vertex partition, is in fact the following maximum subgraph problem 
in disguise: 
find a largest subgraph where every vertex has one colour for its incident edges 
(Vertex-Monochromatic Subgraph), 
or, equivalently, delete fewest edges to destroy all alternating paths 
(Alternating Path Removal).
This multiple points of view gives us a better understanding of these problems,
and is quite useful in studying them.

We are mainly interested in algorithmic issues of Coloured Clustering, 
and will consider polynomial-time algorithms, NP-completeness, and also FPT algorithms
for the two natural parameters from the subgraph point of view: 
numbers of edges inside (stable edges) and outside (unstable edges), 
respectively, the solution subgraph.



 §.§ Main results


We now summarize our main results for Coloured Clustering, 
where m and n, respectively, are numbers of edges and vertices in G.
These results can be translated directly into corresponding results for 
Vertex-Monochromatic Subgraph and Alternating Path Removal.



  * We obtain an O(m^3/2log n)-time algorithm for edge-bicoloured graphs G by 
a reduction to the classical minimum cut problem,  
which improves the O(m^3/2n)-time algorithm of Angel et al. <cit.> 
based on independent sets in bipartite graphs.
We also give linear-time algorithms for the special case when G is a complete graph 
(see 4).


  * We push the NP-completeness of the problem to edge-tricoloured planar 
bipartite graphs of maximum degree four (see 5).


  * We derive FPT algorithms for the problem when we take the numbers 
of stable edges and unstable edges, respectively, as parameter k,
which is uncommon for most problems parameterized in this way.
Furthermore, we obtain a kernel with at most 4k vertices and 2k^2+k edges
for the latter problem (see 6).




 §.§ Related work


Both monochromatic subgraphs and alternating paths are at least half-century old, 
and there is a huge number of papers in the literature dealing with 
them graph theoretically <cit.>.
However, we are not aware of any work on these two subjects 
that is directly related to the algorithmic problems we study in this paper.


In the literature, papers by Angel et al. <cit.> and Ageev and Kononov <cit.>
seem to be the only work that directly study Coloured Clustering.
Angel et al. obtain an LP-based 1/e^2-approximation algorithm for the problem in general, 
which is improved to a 7/23-approximation algorithm by Ageev and Kononov.
Angel et al. also give a polynomial-time algorithm for the problem on edge-bicoloured
graphs by a reduction to the maximum independent set problem on bipartite graphs,
but show the NP-completeness of the problem for edge-tricoloured bipartite graphs.




§ DEFINITIONS


An edge-coloured graph G is a simple graph where each edge e has a unique
colour ψ(e) ∈{1, …, t} for some positive integer t.
We say that G is edge-bicoloured if t = 2, and edge-tricoloured
if t =3.
Unless specified otherwise, we use m and n, respectively,
for the numbers of edges and vertices of G.

A vertex v is colourful if its incident edges have at least 
two different colours, and monochromatic otherwise.
A subgraph H of G is vertex-monochromatic if all vertices in H
are monochromatic vertices of H, and edge-monochromatic if all edges in H 
have the same colour. 

A conflict pair is a pair of adjacent edges of different colours,
and an alternating path is a simple path where every pair of consecutive
edges forms a conflict pair.
The edge-conflict graph of G, denoted X(G), is an uncoloured graph
where each vertex represents an edge of G 
and each edge corresponds to a conflict pair in G.

A vertex colouring f of G assigns to each vertex v of G a colour 
f(v) ∈{1, …, t} for some positive integer t. 
For a vertex colouring f of G, an edge uv is stable if its colour
ψ(uv) = f(u) = f(v), and unstable otherwise.

Angel et al. <cit.> have recently proposed the following problem,
which is in fact, as we will see shortly, the problem of finding the largest
vertex-monochromatic subgraph in G in disguise (see equal).


Coloured Clustering 

Input: Edge coloured graph G and positive integer k. 

Question: Is there a vertex colouring of G that produces at least k stable edges?


The following problem is concerned with purging conflict-pairs
(equivalently, alternating paths) by edge deletion, and is
the complementary problem of Coloured Clustering (see same).


Conflict-Pair Removal 

Input: Edge coloured graph G and positive integer k. 

Question: Does G contain at most k edges E' such that G - E' 
contains no conflict pair?





§ BASIC PROPERTIES


Although Coloured Clustering is defined by vertex partition 
(i.e., vertex colouring), it is in fact a maximum subgraph problem in disguise.
To see this, we first observe the following equivalent properties for
edge-coloured graphs.  

equalThe following statements are equivalent for any edge-coloured graph G:

(a). G is vertex-monochromatic.

(b). Every component of G is edge-monochromatic.

(c). G has no alternating path. 

(d). G has no conflict pair.


The equivalence between (a) and (b) is obvious, and so is the equivalence 
between (c) and (d) as a conflict pair is itself an alternating path. 
Furthermore, it is again obvious that G contains a conflict pair 
if and only if G has a colourful vertex, and therefore (a) and (d) are equivalent.
It follows that the four statements are indeed equivalent.


Observe that for any vertex colouring of G, the subgraph formed by stable edges
is vertex-monochromatic, and hence Coloured Clustering
is actually equivalent to finding a largest vertex-monochromatic subgraph,
which in turn is equivalent to deleting fewest edges to destroy all conflict pairs.
This gives us the following complementary relation between Coloured Clustering
and Conflict-Pair Removal.

same
There is vertex colouring for G that produces at least k stable edges if and only if 
G contains at most m-k edges E' such that G-E' has no conflict pair.


The bilateral relation between Coloured Clustering and Conflict-Pair Removal 
is akin to that between the classical Independent Set and Vertex Cover.
In fact, the former two problems become exactly the latter two in the edge-conflict 
graph X(G) of G (see conflict-graph).

It is very useful to view Coloured Clustering as an edge deletion problem, 
instead of a vertex partition problem, which often makes things easier. 
For instance, it becomes straightforward to obtain the following result 
of Angel et al. <cit.> for X(G). 

conflict-graph[Angel et al.<cit.>]
An edge-coloured graph G admits a vertex colouring that produces at least k 
stable edges if and only if the edge-conflict graph X(G) of G has 
an independent set of size at least k.


By same, the former statement is equivalent to deleting at most 
m-k edge to obtain a graph without conflict pair, which is the same as X(G)
has a vertex cover of size at most m-k, and hence X(G) has an independent 
set of size at least k.




§ ALGORITHMS FOR EDGE-BICOLOURED GRAPHS


Although Coloured Clustering is NP-complete for edge-tricoloured graphs <cit.>,
Angel et al. <cit.> have obtained an O(m^3/2n)-time algorithm for the problem
on edge-bicoloured graphs G by reducing it to the maximum independent set problem on
bipartite graphs X(G). 
In this section, we will give a faster O(m^3/2log n)-time algorithm
by considering Conflict-Pair Removal, which leads us to a simple reduction
to a minimum cut problem.
We also give a linear-time algorithm for the problem on edge-bicoloured complete graphs.



 §.§ Faster algorithm


One bottleneck of the algorithm of Angel et al. lies in the size of the edge-conflict
graph X(G) which contains O(m) vertices and O(mn) edges.
Here we use a different approach of reduction to construct a digraph G' with only 
O(m) vertices and edges, and then solve an equivalent minimum cut problem on G'
to solve our problem.

Let G = (V, E) be an edge-bicoloured graph with colours {1,2},
and consider Conflict-Pair Removal.
Our idea is to transform every conflict pair in G into an (s, t)-path 
in a digraph G' with source s and sink t.
For this purpose, we construct digraph G' from G as follows
(see mincut for an example of the construction):


  * Take graph G and add two new vertices — source s and sink t.

  * For each edge v_iv_j of G, create a new vertex v_ij to represent edge v_iv_j.
If v_iv_j has colour 1 then replace it by two edges v_ijv_i and v_ijv_j 
and add edge sv_ij.
Otherwise replace the edge by two edges v_iv_ij and v_jv_ij 
and add edge v_ijt.


mincut2.1Digraph G' from graph G, where shaded vertices in G' 
correspond to edges in G and thick edges indicate corresponding solution edges.mincut.fig

An (s, t)-cut in G' is a set of edges whose deletion disconnects 
sink t from source s.
Let v_iv_j and v_iv_j' be an arbitrary conflict pair of G.
Without loss of generality, we may assume that v_iv_j has colour 1
and v_iv_j' has colour 2.
By the construction of G', there is a unique (s, t)-path

    P(j,i,j')  = sv_ij, v_ijv_i, v_iv_ij', v_ij't

in G' that goes through vertices v_ij and v_ij'.
For convenience, we refer to edges sv_ij and v_ij't
as external edges and the other two edges as middle edges.
Edges v_iv_j and v_iv_j' of G correspond to external edges
sv_ij and v_ij't, respectively, in G'.
We also call an (s, t)-cut a normal cut if
the cut contains no middle edge of any P(j,i,j').

mincut
Let E' be a set of edges in G.
Then G - E' contains no conflict pair if and only if corresponding edges
of E' in G' form a normal (s, t)-cut of G'.


There is a one-to-one correspondence between conflict pair v_iv_j 
and v_iv_j' in G and external edges sv_ij and v_ij't in G' 
in such a way that the conflict pair is destroyed if and only if 
the (s, t)-path P(j,i,j') is disconnected. This clearly implies the lemma.


The above lemma enables us to solve Conflict-Pair Removal on edge-bicoloured
graphs by reducing it to the minimum cut problem, which yields a faster algorithm.

bicolouredConflict-Pair Removal for edge-bicoloured graphs G can be
solved in O(m^3/2log n).


By mincut, we can reduce our problem on G to the minimum normal (s, t)-cut
problem on digraph G'.
Observe that for any (s, t)-cut, we can always replace a middle edge by 
an external edge without increasing the size of the cut.
Therefore we need only solve the minimum (s, t)-cut problem on digraph G',
which can be accomplished by the maximum flow algorithm of Goldberg and Rao <cit.>.
 
For the running time of the algorithm, we first note that G' contains N = m + n + 2 vertices
and M = 3m edges, and can be constructed in O(m + n) time.
Since every edge of G' has capacity 1, Goldberg and Rao's algorithm takes  
O(min(N^2/3, M^1/2)M log N^2/M) time,
which gives us O(m^3/2log n) time as M, N = O(m).


bicolouredColoured Clustering for edge-bicoloured graphs G can be
solved in O(m^3/2log n) time.




 §.§ Complete graphs
 

We now turn to the special case of Coloured Clustering when G = (V, E) 
is an edge-bicoloured complete graph, and present a linear-time algorithm.
Let f be a vertex-2-colouring of G that colours vertices V_1 by colour 1
and vertices V_2 by colour 2.
For a vertex v, let d_1(v) be the number of edges of colour 1 incident with v.
Let m_1 be the number of edges with colour 1.
We can completely determine the number of stable edges produced by f as follows.

clique
For a vertex-2-colouring f of an edge-bicoloured complete graph G, the number S_f
of stable edges produced by f equals

    ∑_v ∈ V_1 d_1(v) +  |V_2|  2 - m_1.


Let A and B be numbers of edges of colour 1 
in G[V_1] and G[V_2] respectively.
By the definition of stable edges, we have

    S_f = A + (|V_2|  2 - B)

as G[V_2] is a complete graph.
On the other hand,  B  = m_1 - C,
where C is the number of edges of colour 1 covered by vertices V_1.
Therefore

    S_f = A + |V_2|  2 + C - m_1,

and the lemma follows from the fact that  
A + C = ∑_v ∈ V_1 d_1(v).


With the formula in the above lemma, we can easily and efficiently 
solve Coloured Clustering for edge-bicoloured complete graphs.

clique
Coloured Clustering can be solve in O(n^2) for edge-bicoloured complete graphs.


From clique, we see that once we fix the size of V_1 to be k,
S_f is maximized when we choose k vertices v with largest d_1(v)
as vertices in V_1.
Therefore we can compute the maximum value of S_f for each 0 ≤ k ≤ n,
and find an optimal vertex-2-colouring for G.
The whole process clearly takes O(n^2) time as we can first sort vertices 
according to d_1(v).


We can also use a similar idea to solve Coloured Clustering in O(n^2) time
for edge-bicoloured complete bipartite graphs, which will appear in our full paper.



§ NP-COMPLETENESS


Angel et al. <cit.> have shown the NP-completeness of 
Coloured Clustering for edge-tricoloured bipartite graphs.
In this section, we further push the intractability of the problem
to edge-tricoloured planar bipartite graphs of bounded degree.
Recall that a vertex colouring is proper if the two ends 
of every edge receive different colours.

planar
Coloured Clustering is NP-complete for edge-tricoloured 
planar bipartite graphs of maximum degree four.


Garey, Johnson and Stockmeyer <cit.> proved the NP-completeness of Independent Set 
on cubic planar graphs, and we give a reduction from this restricted case of 
Independent Set to our problem.
For an arbitrary cubic planar graph G = (V, E) with V = { v_1, …, v_n }, 
we construct an edge-tricoloured planar bipartite graph G' = (V', E') of 
maximum degree four as follows:



  * Compute a proper vertex 3-colouring ψ of G.


  * For each edge v_iv_j ∈ E, subdivide it by a new vertex v_ij
(i.e., replace edge v_iv_j by two edges v_iv_ij and v_ijv_j),
and colour edges v_iv_ij and v_ijv_j by ψ(v_i) and ψ(v_j) respectively.


  * For each vertex v_i ∈ V, add a new vertex v^*_i and edge v_iv_i^*,
and colour edge v_iv_i^* by a colour in {1,2,3} different from ψ(v_i).


It is clear that G' is an edge-tricoloured planar bipartite graphs of maximum degree four.
By Brooks' Theorem, every cubic graph except K_4 admits a proper vertex 3-colouring,
and we can use an algorithm of Lovász <cit.> to compute a proper 
vertex 3-colouring of a cubic graph in linear time. 
Therefore, the above construction of G' takes polynomial time.
We claim that G has an independent set of size k if and only if G'
admits a vertex colouring that produces k + |E| stable edges.

Suppose that G contains an independent set I of size k.
We define a vertex-3-colouring f of G' as follows:


  * For each vertex v_i^* ∈ V^*, set f(v_i^*) to be the colour of edge v_iv_i^*. 


  * For each vertex v_i ∈ V, set f(v_i) to be the colour of edge v_iv^*_i if v_i ∈ I
and f(v_i) = ψ(v_i) otherwise.


  * For each vertex v_ij, set f(v_ij) to be ψ(v_i) if v_i ∉I 
and ψ(v_j) otherwise.


Clearly, f produces k stable edges v_iv_i^* after Step 2. 
For any vertex v_ij, since I contains at most one of v_i and v_j,
exactly one of v_iv_ij and v_ijv_j becomes a stable edge after Step 3.
Therefore f produces k+ |E| stable edges for G'.

Conversely, call each edge v_iv_i^* an outside edge,
and let f' be a vertex 3-colouring of G' that produces k + |E| stable edges
and also minimizes the number of outside edges among these stable edges.
Let 

    I = { v_i: }.

For every vertex v_ij in G', since edges v_iv_ij and v_ijv_j have different colours,
at most one of these two edges is a stable edge for any vertex colouring of G'.
It follows that at least k stable edges are formed by outside edges and hence
I contains at least k vertices.

We claim that I is an independent set of G.
Suppose to the contrary that for some vertices v_i, v_j ∈ I, v_iv_j is an edge of G.
First we note that amongst all edges incident with v_i,  
v_iv^*_i is the only stable edge under f' 
as f'(v_i) ≠ψ(v_i), and similar situation holds for all edges incident with v_j.
In particular, neither v_iv_ij nor v_ijv_j is a stable edge.
We now recolour both vertices v_i and v_ij by the colour of edge v_iv_ij
(note that v_ij may have received that colour already under f') 
to obtain a new vertex 3-colouring f” (see npc for an example of the situation).

npc1.8(a) Situation under vertex colouring f'.  
(b) Situation after recolouring vertices v_i and v_ij. 
Stable edges are indicated by thick edges.npc.fig

Comparing with colouring f', this new colouring f” reduces one stable edge 
(namely, edge v_iv_i^*), but produces a new stable edge v_iv^*_i 
(and probably also other new stable edges).
Therefore f” produces at least k + |E| stable edges that contains 
one less outside edges than f', contradicting the choice of f'.
This contradiction implies that I is indeed an independent set of G with 
at least k vertices, and hence the theorem holds.


planar
Conflict-Pair Removal is NP-complete for edge-tricoloured
planar bipartite graphs of maximum degree four.




§ FPT ALGORITHMS


We now turn to the parameterized complexity of Coloured Clustering,
and give FPT algorithms for the problem with respect to both the number 
of stable edges and the number of unstable edges as parameter k.
This is quite interesting as it is uncommon for a problem to admit
FPT algorithms both ways when parameterized in this manner.



 §.§ Stable edges


First we take the number of stable edges produced by a vertex colouring 
of G as parameter k, and use Coloured Cluster[k] to denote this
parameterized problem.  
We will give an FPT algorithm that uses random partition in the spirit of 
the colour coding method of Alon, Yuster and Zwick <cit.>, which 
implies an FPT algorithm for Independent Set[k] in edge-conflict graphs.
Note that if the number t of colours in G is a constant, 
then the problem is trivially solved in FPT time as it contains a trivial kernel 
with at most kt edges and hence 2kt vertices.
Also note that the problem is not as easy as it looks, for it contains
the maximum matching problem as a special case when all edges have different colours.

Our idea is to randomly partition vertices of G into k parts V_1, …, V_k
in a hope that a k-solution consists of k_i stable edges, where ∑_i=1^k k_i = k,
in each G[V_i]. Indeed we have a good chance to succeed in this way.


Algorithm Coloured-Clustering[k]

Randomly partition vertices V of G into V_1,⋯,V_k.

Compute the most frequently used colour c_i for  each G[V_i]. 

Colour all vertices in V_i by c_i.



chanceFor any yes-instance of  Coloured Cluster[k],
the vertex colouring constructed by Algorithm Coloured-Clustering[k] 
has probability at least k^-2k to produce at least k stable edges.

Consider a vertex colouring of G that produces at least k stable edges E',
which clearly have at most k different colours.
Let E'_i be edges in E' of colour c_i and let k_i = |E'_i| for 1 ≤ i ≤ k.
We estimate the probability that all edges of E'_i lie in G[V_i].
A vertex has probability k^-1 to be in V_i, and hence 
the above event happens with probability at least k^-2k_i 
as E'_i contains at most 2k_i vertices. 
It follows that, with probability at least 

    k^- ∑_i=1^k 2k_i = k^-2k,

all edges of each E'_i lie entirely inside G[V_i].
Therefore each G[V_i] contains at least k_i edges of same colour c_i,
which can be made stable by colouring all vertices in G[V_i] by colour c_i.
It follows that the algorithm produces at least k stable edges with probability k^-2k.


The algorithm runs in O(k^2k(m+n)) expected time, and can be made into a 
deterministic FPT algorithm by standard derandomization with a family of
perfect hashing functions.

stable
Coloured Cluster[k] can be solved in FPT time.




 §.§ Unstable edges


Now we take the number of unstable edges in a vertex colouring as parameter k,
and use Conflict-Pair Removal[k] to denote this parameterized problem.
By a result of Angel et al. <cit.>, the problem is equivalent to finding a
vertex cover of size k in the edge-conflict graph X(G) of G, 
and hence admits an FPT algorithm by transforming it to the k-vertex cover problem 
in X(G).
However the time for the transformation takes O(mn) time as X(G) contains O(m)
vertices and O(mn) edges, and the total time for the algorithm takes 
O(mn + 1.2783^k) time. 
Here we combine kernelization with weighted vertex cover to obtain
an improved algorithm with running time O(m+n+1.2783^k).

To start with, we construct in linear time the following edge-coloured weighted graph G^*, 
called condensed graph, by representing monochromatic vertices of one colour by a single
vertex, and then parallel edges between two vertices by a single weighted edge.
See condense for an example of the construction.

Step 1. For each colour c, contract all monochromatic vertices of colour c 
into a single vertex v_c.
 
Step 2. For each pair of adjacent vertices, if there is only one edge between them,
then set the weight of the edge to 1, otherwise replace all parallel edges between them 
by a single edge of the same colour[All such parallel edges have the same colour 
as they correspond to edges between a vertex and monochromatic vertices of the same colour.]
and set its weight to be the number of replaced parallel edges.

condense2(a) Edge-coloured graph G where each dashed ellipse 
indicates monochromatic vertices of same colour.
(b) The condensed graph G^* of G where an edge of weight more than 1 
has its weight as the superscript of its colour.condense.fig

It turns out that the clustering problem on G is equivalent to a weighted version of the problem 
on the condensed graph G^*.

condense
Graph G has at most k unstable edges if and only if 
G^* has unstable edges of total weight at most k.

By the construction of G^*, we have the following correspondence 
between edges in G and G^*: 
every edge in G between two colourful vertices remains so in G^*, and 
for any colourful vertex v, all edges between v and monochromatic vertices 
of colour c correspond to edge vv_c in G^*.
Also all monochromatic vertices in G^* form an independent set.


Now suppose that G has a vertex colouring f that produces k unstable edges.
Without loss of generality, we may assume that every monochromatic vertex v in G
has its own colour as f(v) since this will not increase unstable edges.
For this f, we have a natural vertex colouring f^* for G^*: the colour of each vertex
retains its colour under f.
It is obvious that an edge in G^* between two colourful vertices is an unstable edge under
f^* 
if and only if it is an unstable edge in G under f.
For edges E_c(v) in G between a colourful vertex v and monochromatic vertices 
with colour c, either all edges in E_c(v) are stable or all are unstable
as f colours all these monochromatic vertices by colour c, 
implying that all edges in E_c(v) are unstable under f if and only if 
vv_c is unstable under f^*.
Therefore f^* produces unstable edges of total weight k in G^*.

Conversely, suppose that G^* contains a set U of unstable edges of total weight k, and
let U' be the corresponding k edges in G.
Clearly G - U' contains no conflict pair, and hence G has at most k unstable edges.



Further to the above lemma, G^* can be regarded as a kernel as its size
is bounded by a function of k whenever G has at most k unstable edges.
Note that the bounds in the following lemma are tight.

kernel
If G has at most k unstable edges, then G^* has at most 4k vertices and 2k^2+k edges.

Let [C, M] be the cut that partitions the vertices of G 
into colourful vertices C and monochromatic vertices M.
Let A be the set of unstable edges inside G[C], and B the set of unstable edges across the cut.
Observe that each edge of A is incident with at most two vertices of C, 
and each edge of B is incident with one vertex of C.
Furthermore, every colourful vertex is incident with at least one unstable edge.
Therefore |C| ≤ 2|A|+|B| ≤ 2k.

Now consider the condensed graph G^*, and note that the cut [C, M] corresponds to the cut [C,
M^*]
for monochromatic vertices M^* of G^*.
Furthermore, A consists of unstable edges inside G^*[C], and
B corresponds to unstable edges B^* across [C, M^*] and |B^*| ≤ |B|.

In G^*, every vertex in C is incident with at most one stable edge in  [C, M^*].
Therefore [C, M^*] contains at most

    |C| + |B^*| ≤ (2|A|+|B|)+|B^*| ≤ 2(|A|+|B|) = 2k

edges, and hence M^* contains at most 2k vertices.
It follows that G^* contains at most 4k vertices, and at most 
2k  2+2k = 2k^2+k edges as G^*[M^*] is edgeless.


With condense and kernel in hand, we obtain the following FPT algorithm
for Conflict-Pair Removal[k]


Algorithm Conflict-Pair-Removal[k] 


Construct the condensed graph G^* from G; 

if G^* c̄ontains more than 4k vertices or 2k^2+k edges 

	 then return “No” and halt; 

Construct the edge-conflict X(G^*) of G^*;

if X(G^*) has a vertex cover of weight at most k 

	 then return “Yes”

	 else return “No”.



Conflict-Pair Removal[k] can be solved in O(m+n+1.2783^k) time.

The correctness of the algorithm follows from condense and kernel, 
and we analyze the running time of the algorithm.
The construction of the condensed graph G^* clearly takes O(m+n) time,
and the construction of the edge-conflict graph X(G^*) takes O(k^3) time 
as G^* contains O(k) vertices and O(k^2) edges.
Note that X(G^*) contains O(k^2) vertices and O(k^3) edges.
Since it takes O(kn + 1.2783^k) to solve the weighted vertex cover problem <cit.>, 
it takes O(k^3 + 1.2783^k) = O(1.2783^k) to solve the problem for G^*,
and hence the overall time is O(m + n + 1.2783^k).





§ CONCLUDING REMARKS


We have revealed that Coloured Clustering, a vertex partition problem, 
is in fact subgraph problems Vertex-Monochromatic Subgraph and
Alternating Path Removal in disguise, and demonstrated the usefulness of 
this multiple points of view in studying these problems.
Indeed, our improved algorithm for edge-bicoloured graphs and FPT algorithms 
for general edge-coloured graphs have benefited a lot from 
the perspective of Conflict-Pair Removal.
We now briefly discuss a few open problems in the language of monochromatic subgraphs
and alternating paths for readers to ponder. 
 

Question 1. For edge-bicoloured graphs, is there a faster algorithm 
for deleting fewest edges to obtain a vertex-monochromatic subgraph?


There seems to be a good chance to solve the problem faster than our algorithm,
and one possible approach is to reduce the number of vertices in the reduction 
to minimum cut from the current O(m) to O(n).


Question 2. For Conflict-Pair Removal on general 
edge-coloured graphs, is there an r-approximation algorithm for some constant r < 2?

The problem admits a simple 2-approximation algorithm through its connection with
Vertex Cover, and seems easier than the latter problem.
It is possible that we can do better for the problem, perhaps through ILP relaxation. 


Question 3. For edge-coloured graphs, 
does the problem of finding a vertex-monochromatic subgraph with at least k edges 
admit a polynomial kernel?


The above problem is appealing for its connection with the classical maximum matching 
problem.
On one hand, we may use a maximum matching of G as a starting point for 
a polynomial kernel; and on the other hand if we can obtain a polynomial kernel of G
in o(m√(n)) time, we may use the kernel to speed up maximum matching algorithms.
Of course, it may be the case that the problem admits no polynomial kernel unless
NP ⊆ coNP/poly.


Question 4. For edge-coloured graphs, 
is there an FPT algorithm for the problem of destroying 
all alternating cycles by deleting at most k edges?


Although the definition of the problem resembles that of Alternating Path Removal,
the problem seems much more difficult as the problem does not have a finite forbidden
structure like conflict pair for the latter problem.
We note that the problem is NP-complete by a simple reduction from Vertex Cover.









Ageev
Ageev, A., and Kononov, A., 
Improved Approximations for the Max k-Colored Clustering Problem.
In: International Workshop on Approximation and Online Algorithms 2014, LNCS 8952 (pp. 1-10), 2015. 

Alon
Alon, N., Yuster, R., and Zwick, U.,
Color-coding,  
Journal of the ACM 42:844–856, 1995

Angel
Angel, E., Bampis, E., Kononov, A., Paparas, D., Pountourakis, E., and Zissimopoulos, V., 
Clustering on k-edge-colored graphs.
Discrete Applied Mathematics, 211:15-22, 2016.

Bang
Bang-Jensen, J., and Gutin, G.,
Alternating cycles and paths in edge-coloured multigraphs: a survey. 
Discrete Mathematics, 165:39-60, 1997.

Bansal
Bansal, N., Blum, A., and Chawla, S.,
Correlation clustering. Machine Learning, 56(1-3):89-113, 2004.

Cai
Cai, L., 
Fixed-parameter tractability of graph modification problems for hereditary properties.
Information Processing Letters, 58(4):157–206, 1996.

Chen
Chen, J., Kanj, I. A., and Xia, G.,
Improved upper bounds for vertex cover. 
Theoretical Computer Science, 411(40-42):3736-3756, 2010.

Garey
Garey, M. R., Johnson, D. S., and Stockmeyer, L.,
Some simplified NP-complete graph problems.
Theoretical computer science, 1(3):237-267, 1976.

Gold
Goldberg, A. V., and Rao, S.,
Beyond the flow decomposition barrier. 
Journal of the ACM (JACM), 45(5):783-797, 1998.

Kano
Kano, M., and Li, X.,
Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. 
Graphs and Combinatorics, 24(4):237-263, 2008.

Lovasz
L. Lovász,
Three short proofs in graph theory.
J. Combin. Theory Ser. B, 19:269-271, 1975.

Nied
Niedermeier, R., and Rossmanith, P.,
On efficient fixed-parameter algorithms for weighted vertex cover. 
Journal of Algorithms, 47(2):63-77, 2003.



plain

