Algorithms and hardness results for happy
coloring problems

arXiv:1705.08282v1 [] 23 May 2017

N. R. Aravind1 , Subrahmanyam Kalyanasundaram1 , Anjeneya Swami Kare1? ,
and Juho Lauri2??
1

Department of Computer Science and Engineering
Indian Institute of Technology
Hyderabad, India
{aravind,subruk,cs14resch01002}@iith.ac.in
2
Tampere University of Technology, Finland
juho.lauri@tut.fi

Abstract. In a vertex-colored graph, an edge is happy if its endpoints
have the same color. Similarly, a vertex is happy if all its incident edges
are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum
Happy Edges (k-MHE) problem: given a partially k-colored graph G,
find an extended full k-coloring of G maximizing the number of happy
edges. When we want to maximize the number of happy vertices, the
problem is known as Maximum Happy Vertices (k-MHV). We further
study the complexity of the problems and their weighted variants. For instance, we prove that for every k ≥ 3, both problems are NP-complete for
bipartite graphs, and k-MHV remains hard for split graphs. In terms of
exact algorithms, we show both problems can be solved in time O∗ (2n ),
and give an even faster O∗ (1.89n )-time algorithm when k = 3. From a
parameterized perspective, we give a linear vertex kernel for Weighted
k-MHE, where edges are weighted and the goal is to obtain happy edges
of at least a specified total weight. Finally, we prove both problems are
solvable in polynomial-time when the graph has bounded treewidth or
bounded neighborhood diversity.

1

Introduction

Analyzing large networks is of fundamental importance for a constantly growing
number of applications. In particular, how does one mine e.g., social networks to
provide valuable insight? A basic observation concerning the structure of social
networks is homophily, that is, the principle that we tend to share characteristics
with our friends. Intuitively, it seems believable our friends are similar to us in
terms of their age, gender, interests, opinions, and so on. In fact, this observation
is well-known in sociology (see e.g., [1,2,3]). For example, imagine a network of
?

??

Faculty member of University of Hyderabad. This work is carried out as part of his
PhD program at IIT Hyderabad.
Work partially supported by the Emil Aaltonen Foundation (J.L.).

1

supporters in a country with a two-party system. In order to check whether there
is homophily by political stance (i.e., a person tends to befriend a person with
similar political beliefs), we could count the number of edges between two people
of opposite beliefs. If there were no such edges, we would observe homophily in
an extreme sense. It is characteristic of social networks that they evolve over
time: links tend to be added between people that share some characteristic. But
given a snapshot of the network, how extensively can homophily be present? For
instance, how far can an extreme ideology spread among people some of whom
are “politically neutral”?
We abstract these questions regarding the computation of homophily as follows. Consider a vertex-colored graph G = (V, E). We say an edge is happy if
its endpoints have the same color (otherwise, the edge is unhappy). Similarly,
a vertex is happy if it and all its neighbors have the same color (otherwise, the
vertex is unhappy). Equivalently, a vertex is happy when all of its incident edges
are happy. Let S ⊆ V , and let c : S → [k] be a partial vertex-coloring of G. A
full coloring c0 : V → [k] is an extended full coloring of c if c(v) = c0 (v) for all
v ∈ S. In this paper, we consider the following coloring problems.
Weighted Maximum Happy Edges (Weighted k-MHE)
Instance: A graph G = (V, E), a partial vertex-coloring c : S ⊆ V → [k], a
weight function w : E → N, and an integer `.
Question: Is there an extended full coloring c0 of c such that the sum of
the weights of the happy edges is at least `?
Weighted Maximum Happy Vertices (Weighted k-MHV)
Instance: A graph G = (V, E), a partial vertex-coloring c : S ⊆ V → [k], a
weight function w : V → N, and an integer `.
Question: Is there an extended full coloring c0 of c such that the sum of
the weights of the happy vertices is at least `?
We also consider the unweighted versions of the problems obtained by letting
the weight of each edge or vertex be one. We refer to these problems as k-MHE
and k-MHV, respectively.
Previous work. Zhang and Li [4] proved that for every k ≥ 3, the problems
k-MHE and k-MHV are NP-complete. However, when k = 2, they gave algorithms running in time O(min{n2/3 m, m3/2 }) and O(mn7 log n) for 2-MHE and
2-MHV, respectively. Towards this end, the authors used max-flow algorithms
(2-MHE) and minimization of submodular functions (2-MHV). Moreover, the
authors presented approximation algorithms with approximation ratios 1/2 and
max{1/k, Ω(∆−3 )} for k-MHE and k-MHV, respectively, where ∆ is the maximum degree of the graph. Later on, Zhang, Jiang, and Li [5] gave improved
algorithms with approximation ratios 0.8535 and 1/(∆ + 1) for k-MHE and
k-MHV, respectively. In [6], a subset of the current authors proved that both
problems are solvable in polynomial time for trees.
Perhaps not surprisingly, the happy coloring problems are tightly related to
cut problems. Indeed, the k-MHE problem is a generalization of the following
2

Multiway Uncut problem [7]. In this problem, we are given a weighted undirected graph G = (V, E) and a terminal set S = {s1 , s2 , . . . , sk } ⊆ V . The goal
is to find a partition of V into classes V1 , . . . , Vk such that each class contains
exactly one terminal and the total weight of the edges not cut by the partition
is maximized. We obtain the Multiway Uncut problem as a special case of
k-MHE, when each color is used to precolor exactly one vertex. We also mention
that the complement of the Multiway Uncut problem is the Multiway Cut
problem that has been studied before (see e.g., [8,9]). There are known (parameterized) algorithms for the Multiway Cut problem with the size of the cut `
as the parameter. In this regard, the fastest known algorithm runs in O∗ (1.84` )
time [10].
Our results. We further study the complexity of happy coloring problems
including their unweighted variants. Our paper is organized as follows:
– In Section 3, we focus on hardness results of the problems and their unweighted variants for special graph classes. We prove that for every k ≥ 3,
the problem k-MHV is NP-complete for split graphs and bipartite graphs.
This extends the hardness result of Zhang and Li [4] for general graphs.
Similarly, we show that k-MHE remains NP-complete for bipartite graphs,
and that its weighted variant is hard for complete graphs.
– In Section 4, we consider exact exponential-time algorithms for the happy
coloring problems. The naive brute force runs in k n nO(1) time, but we show
that for every k ≥ 3, there is an algorithm running in time O∗ (2n ), where n
is the number of vertices in the input graph. Moreover, we prove that this is
not optimal for every k by giving an even faster O∗ (1.89n )-time algorithm
for both 3-MHE and 3-MHV.
– In Section 5, we show that despite its hardness on complete graphs, the
problem Weighted k-MHE admits a small kernel of size k + ` on general
graphs. The ingredients of the kernel are a polynomial-time algorithm for
Weighted k-MHE when the uncolored vertices induce a forest combined
with simple reduction rules.
– Finally, in Section 6, we study the complexity of both problems for sparse
graphs (i.e., small treewidth) and the simplest of dense graphs (i.e., small
neighborhood diversity). When either parameter is bounded, we show both
problems admit polynomial-time algorithms.

2

Preliminaries

We use standard asymptotic notation. Sometimes, we write f (n) = O∗ (g(n)) if
f (n) = O(g(n)poly(n)), where poly(n) represents any polynomial in n. For a
positive integer n, we use [n] to denote the set {1, 2, . . . , n}.
Unless specified otherwise, all graphs we consider are simple and undirected.
Let G = (V, E) be an undirected graph. To reduce clutter, we use the shorthand
uv to denote an edge {u, v} ∈ E. Two vertices u, v ∈ V are adjacent or neighbors
if uv ∈ E. The set of neighbors of v is the open neighborhood of v, denoted by
3

Table 1: Summary of our hardness results for the unweighted problem variants.
Graph class k-MHE

k-MHV

Bipartite
Complete
Split

NPC
P
NPC

NPC
P
?

N (v). The closed neighborhood of v, denoted by N [v], is defined as N [v] =
N (v) ∪ {v}. More generally, for V 0 ⊆ V , we write N (V 0 ) and N [V 0 ] to denote
the set of all neighbors in the open neighborhood and closed neighborhood of
each vertex in V 0 , respectively. For graph-theoretic concepts not defined here,
we refer the reader to [11].
A parameterized problem is a language L ⊆ Σ ∗ × N, where Σ is a fixed,
finite alphabet. For an instance (x, k) ∈ Σ ∗ × N, we call k the parameter. The
parameterized problem L is fixed-parameter tractable (FPT) when there is an
algorithm A, a computable function f : N → N, and a constant c such that,
given (x, k) ∈ Σ ∗ × N, the algorithm A correctly decides whether (x, k) ∈ L in
time bounded by f (k) · |x|c . An equivalent way of proving a problem is FPT
is by constructing a kernel for it. A kernel for a parameterized problem (x, k)
is a polynomial-time algorithm B that returns an equivalent instance (x0 , k 0 ) of
L such that |x0 | ≤ g(k), for some computable function g : N → N. Here, we
say two instances are equivalent if the first is a YES-instance iff the second is
a YES-instance. Given a parameterized problem, it is a natural to ask whether
it admits a kernel, and moreover whether that kernel is small.3 By small, we
typically mean a polynomial kernel, or even a linear kernel (i.e., g(k) = O(k)).
Kernelization is often discovered through reduction rules. A reduction rule
is a polynomial-time transformation of an instance (x, k) to another instance of
the same problem (x0 , k 0 ) such that |x0 | < |x| and k 0 ≤ k. A reduction rule is
safe when the instances are equivalent. For more on parameterized complexity,
we refer the interested reader to [12].

3

Further hardness results for happy coloring

Zhang and Li [4] showed that both k-MHE and k-MHV are NP-complete for
every k ≥ 3. However, it appears their constructions do not enforce any particular
structure on the graphs that are output. This raises an immediate question: does
the presence of some specific yet allowing graph structure enable us to solve the
problems in polynomial-time? We answer this question in the negative even
for highly structured yet rich graph classes. Our NP-completeness results are
summarized in the Table 1. All of our proofs are by a polynomial-time reduction
from k-MHE, which is NP-complete for every k ≥ 3 by the result of [4].
3

This is abuse of notation: as is commonly done, we call the output of the kernel also
a kernel.

4

3.1

Hardness of k-MHV for special graph classes

Whenever possible, it is beneficial to prove hardness results for k-MHV, as it
is a special case of the more general Weighted k-MHV. We begin by showing
hardness for split graphs, that is, for graphs whose vertex set can be partitioned
into a clique and an independent set. Clearly, complete graphs are also split
graphs, and before proceeding we make the following easy observation.
Proposition 1. Any partial coloring c of the complete graph Kn for any n ≥ 1
can be extended to a full coloring c0 making n vertices happy iff c uses at most
one color. Consequently, the problem k-MHV is solvable in polynomial time for
complete graphs for every k ≥ 1.
Let us then proceed with the hardness result for split graphs. Afterwards, we will
modify the construction slightly to obtain a similar result for bipartite graphs.
Theorem 2. For every k ≥ 3, the problem k-MHV is NP-complete for split
graphs.
Proof. Let I = (G, c, `) be an instance of k-MHE, and let us in polynomial time
construct an instance I 0 = (G0 , c0 , `) of k-MHV. We can safely (and crucially)
assume at least two vertices of G are precolored (in distinct colors), for otherwise
the instance is trivial. We construct the split graph G0 = (C ∪ B, E 0 ∪ E 00 ), where
–
–
–
–

C = {vx | x ∈ V (G)},
B = {ve | e ∈ E(G)},
E 0 = {ve vx | e is incident to x in G}, and
E 00 = {vx vx0 | x, x0 ∈ V (G)}.

That is, C forms a clique and B an independent set in G0 , proving G0 is split.
In particular, observe that the degree of each vertex ve is two. To complete the
construction, we retain the precoloring, i.e., set c0 (vx ) = c(x) for every x ∈ V (G).
The construction is illustrated in Figure 1.
We claim that I is a YES-instance of k-MHE iff I 0 is a YES-instance of
k-MHV. Suppose ` edges can be made happy in G by an extended full coloring
of c. Consider an edge e ∈ E(G) whose endpoints are colored with color i. To
make ` vertices happy in G0 , we give ve and its two neighbors the color i. For
the other direction, suppose ` vertices are happy under an extended full coloring
of c0 . As at least two vertices in C are colored in distinct colors, it follows by
Proposition 1 that all the happy vertices must be in B. Furthermore, the vertices
in B correspond to precisely the edges in E(G), so we are done.
t
u
Theorem 3. For every k ≥ 3, the problem k-MHV is NP-complete for bipartite
graphs.
Proof. We start with the construction of Theorem 2. Modify the split graph G0
by deleting the edges between the vertices in C, i.e., let G0 = (C ∪ B, E 0 ). For
each vx ∈ C, add a path Svx = {vx1 , vx2 , vx3 } along with the edges vx vx1 and vx3 vx .
5

1

e4

3

e1

e3

e5

2

e2

4

ve 1

ve 2

ve 3

ve 4

v1

v2

v3

v4

(a)

ve 5

B

C

(b)

Fig. 1: (a) A graph G of an instance of k-MHE, where white vertices correspond
to uncolored vertices. (b) The graph G transformed into a split graph G0 by the
construction of Theorem 2. The edges between the vertices in C are not drawn.
In other words, each vx forms a 4-cycle with the vertices in Svx . Clearly, we have
that G0 is bipartite as it contains no odd cycles. Arbitrarily choose three distinct
colors from [k], and map them bijectively to Svx . Observe that by construction,
none of the vertices in Svx can be happy under any c0 extending c. This completes
the construction. Correctness follows by the same argument as in Theorem 2.
t
u
3.2

Hardness of k-MHE for special graph classes

In the spirit of the previous subsection, let us begin with an observation regarding
the polynomial-time solvability of the problem for complete graphs.
Proposition 4. The problem k-MHE is solvable in polynomial time for complete graphs for every k ≥ 1.
Proof. Let S denote the set of precolored vertices for the Kn for any n ≥ 1.
Delete edges whose both endpoints are in S, since their happiness is already
determined by the precoloring. Observe that S is now an independent set and
C = V \ S induces a clique. Moreover, every vertex in S is adjacent to every
vertex in C.
Denote by p the most frequent occurrence of any color among the precolored
vertices. For any vertex v ∈ C, regardless of the color we give to v, we can make
at most p edges happy among the edges from the vertices in S to v. Thus, the
number of happy edges is at most p · |C| + |E(C)|. In fact, we can achieve exactly
p · |C| + |E(C)| happy edges by giving a single color to all the vertices in C. More
precisely, we color all the uncolored vertices with the color that is used p times,
completing the proof.
t
u
We remark that for the above proof to hold, we do not need the graph to be
complete. Indeed, the procedure described in the proof can be applied as long
as every precolored vertex is adjacent to every uncolored vertex.
We now turn to hardness results, and show that for every k ≥ 3, the problem
k-MHE is NP-complete for bipartite graphs as well.
6

Theorem 5. For every k ≥ 3, the problem k-MHE is NP-complete for bipartite
graphs.
Proof. Let I = (G, c, `) be an instance of k-MHE, and let us in polynomial time
construct an instance I 0 = (G0 , c, m + `) of k-MHE, where G0 is bipartite. We
obtain G0 by subdividing every edge of G. Observe that if G has n vertices and
m edges, then G0 has n + m vertices and 2m edges. Clearly, G0 is bipartite.
We will now show that G has an extended full coloring making at least `
edges happy iff G0 has an extended full coloring making at least m + ` edges
happy. Let c0 be an extended full coloring of the precoloring c given to G. We
give G0 the same extended full coloring, and give each vertex in v ∈ V (G0 )\V (G)
an arbitrary color that appears on a vertex adjacent to v. Thus, for each edge
in G, we have one extra happy edge in G0 , giving us a total of at least m + `
happy edges. For the other direction, let c0 be an extended full coloring of c
that makes at least m + ` edges happy in G0 . Now, there are at least ` vertices
in V (G0 ) \ V (G) with both of its incident edges happy. These 2` happy edges
correspond to the ` happy edges in G. This concludes the proof.
t
u
We are unable to prove that k-MHE remains NP-complete for split graphs.
However, when weights are introduced, it is easy to see that the problem remains
NP-complete even for complete graphs for every k ≥ 3.
Theorem 6. The problem Weighted k-MHE is NP-complete for complete
graphs for every k ≥ 3.
Proof. Let I = (G, c, `) be an instance of k-MHE, and let us in polynomial time
construct an instance I 0 = (G0 , c0 , w, α · `) of Weighted k-MHE, where G0 is a
complete graph. Here α = n2 − m + 1, where n = |V (G)| and m = |E(G)|. To
construct G0 , first let V (G0 ) = V (G). For each uv ∈ E(G), insert the edge uv to
G0 with weight α. For each uv ∈
/ E(G), insert the edge uv to G0 with weight 1.
0
Clearly, G is a complete graph. It is easy to see G has at least ` happy edges iff
G0 has happy edges of total weight at least α · `.
t
u

4

Exact exponential-time algorithms for happy coloring

In this section, we consider the happy coloring problems from the viewpoint of
exact exponential-time algorithms. Every problem in NP can be solved in time
exponential in the input size by a brute-force algorithm. For k-MHE (k-MHV),
such an algorithm goes through each of the at most k n colorings, and outputs
the one maximizing the number of happy edges (vertices). It is natural to ask
whether there is an algorithm that is considerably faster than the k n nO(1) -time
brute force approach. In what follows, we show that brute-force can be beaten.
Let us introduce the following more general problem.

7

Max Weighted Partition
Instance: An n-element set N , integer d, and functions f1 , f2 , . . . , fd : 2N →
[−M, M ] for some integer M .
Question: A d-partition (S1 , S2 , . . . , Sd ) of N that maximizes f1 (S1 ) +
f2 (S2 ) + · · · + fd (Sd ).
Using an algebraic approach, the following has been shown regarding the complexity of the problem.
Theorem 7 (Björklund, Husfeldt, Koivisto [13]). The Max Weighted
Partition problem can be solved in
– 2n d2 M · nO(1) time and exponential space, and
– 3n d2 M · nO(1) time and polynomial space.
In the following, we observe that the weighted variants of both problems can be
reduced to Max Weighted Partition. This results in an algorithm that is
considerably faster than one running in time k n nO(1) .
Lemma 8. For every k ≥ 1, the problems Weighted k-MHE and Weighted
k-MHV reduce in polynomial time to Max Weighted Partition.
Proof. Consider the claim for an instance I = (G, c, w, `) of Weighted k-MHE.
To construct an instance of Max Weighted Partition, letPN = V (G) \ S,
where S is the set of precolored vertices, let d = k, and let M = uv∈E(G) w(uv).
P
Define fi =
uv∈E(G[Si ∪c−1 (i)]) w(uv), i.e., fi sums the weights of the edges
uv that range over the edge set of the subgraph induced by the union of Si
and c−1 (i), the vertices precolored with color i. Thus, a partition (S1 , . . . , Sk )
maximizing f1 (S1 ) + · · · + fk (Sk ) maximizes the weight of happy edges.
Finally, consider the claimPfor an instance I = (G, c, w, `) of Weighted kMHV. Now, we define fi = v∈Si :∀y∈N (v):y∈(Si ∪c−1 (i)) w(v), i.e., fi sums the
weights of the vertices v for which it holds that
P v and each neighbor y of v
are all colored with color i. Also, we let M = v∈V (G) w(v), but otherwise the
argument is the same as above.
t
u
For some NP-complete problems, the fastest known algorithms run in O∗ (2n )
time, but we do not necessarily know whether (under reasonable complexitytheoretic assumptions) they are optimal. Indeed, could one have an algorithm
that runs in O∗ ((2 − ε)n ) time, for any ε > 0, for either k-MHE or k-MHV? We
prove that at least for some values of k this bound can be achieved. For this, we
recall the following result.
Theorem 9 (Zhang and Li [4]). For k = 2, the problems k-MHE and kMHV can be solved in time O(min{n2/3 m, m3/2 }) and O(mn7 log n), respectively.
We are ready to proceed with the following.
8

Lemma 10. For k = 3, the problems k-MHE and k-MHV can be solved in
0
time O∗ (1.89n ), where n0 is the number of uncolored vertices in the input graph.
Proof. First, consider the claim for an instance I = (G, c, w, `) of k-MHE. Consider a partition S = (S1 , S2 , S3 ) of the uncolored vertices into k = 3 color
classes that maximizes the number of happy edges. In S \ S3 , by the optimality
of S, it must be the case S1 and S2 have a minimum number of crossing edges.
Thus, we can proceed as follows. Observe that in any optimal solution S, there
exists Si ∈ S such that |Si | ≤ n0 /3. The number of subsets of size at most n0 /3
0
0
is 2H(1/3)n < 1.89n , using the well-known bound 2H(1/3) < 1.89, where H(·)
is the binary entropy function (for a proof, see e.g., [14, Lemma 3.13]). Thus,
0
we guess Si by extending it in all possible at most 1.89n ways. Then, for every
such partial coloring, we solve an instance of 2-MHE on the remaining uncolored
vertices in polynomial time by Theorem 9. Combining the bounds, we obtain an
0
algorithm running in time O∗ (1.89n ) for 3-MHE.
The observation is similar for 3-MHV, but we solve an instance of 2-MHV
on V (G) \ N [Si ] instead of V (G) \ Si .
t
u
By Lemma 10 and by combining Theorem 7 with Lemma 8, we arrive at the
following.
Theorem 11. For every k ≥ 3, the problems k-MHE and k-MHV can be solved
0
0
in time O∗ (2n ). When k = 3, the problems are solvable in time O∗ (1.89n ), where
n0 is the number of uncolored vertices in the input graph.

5

A linear kernel for Weighted k-MHE

In this section, we prove that Weighted k-MHE has a kernel of size k + `. Our
strategy to obtain the kernel consists of two parts: first, we will show that there
is a polynomial-time algorithm for the problem where the uncolored vertices
induce a forest. Then, to leverage this algorithm, we apply a set of reduction
rules that shrink the instance considerably, or solve it directly along the way.
5.1

A linear-time algorithm for subproblems of Weighted k-MHE

We show that the Weighted k-MHE problem is polynomial-time solvable when
the uncolored vertices V \S induce a tree, where S is the set of precolored vertices.
When V \ S induces a forest, we run the algorithm for each component in V \ S
independently. The approach we present is based on dynamic programming, and
inspired by the algorithm given in [6].
We define edges touching a subtree to be those edges that have at least one
endpoint in the subtree. We choose any vertex r ∈ V \ S as the root of the tree
induced by V \ S. The vertices of this rooted tree are processed according to its
post-order traversal. At each node, we keep k values. The k values are defined
as follows, for 1 ≤ i ≤ k:
9

– Tv [i] : The maximum total weight of the happy edges touching the subtree
Tv , when the vertex v is colored with color i.
We also define the following expressions:
– Tv [∗] : The maximum total weight of the happy edges touching the subtree
Tv , i.e.,
k

Tv [∗] = max{Tv [i]}.
i=1

(1)

– Tv [ı] : The maximum total weight of the happy edges touching the subtree
Tv , when the vertex v is colored with a color other than i, i.e.,
k

Tv [ı] = max {Tv [j]}.
j=1,j6=i

(2)

If Wp is the total weight of the happy edges in the initial partial coloring,
Wp + Tr [∗] gives us the maximum total weight of the happy edges in G. Now,
we explain how to compute the values Tv [i] for 1 ≤ i ≤ k and for each v ∈ V \ S.
When we say color-i vertices, we mean the vertices precolored with color i.
For a leaf vertex v ∈ V \ S, let v1 , v2 , . . . , vx be the color-i neighbors of v in
G. Then,
x
X
Tv [i] =
w(vvj ).
(3)
j=1

If there are no color-i neighbors for v, then Tv [i] is set to 0.
For a non-leaf vertex v ∈ V \ S, let v1 , v2 , . . . , vx be the color-i neighbors of
v in G and let u1 , u2 , . . . , ud be the children of v in V \ S. Then,
Tv [i] =

x
X
j=1

w(vvj ) +

d
X

max{(w(vuj ) + Tuj [i]), Tuj [ı]}.

(4)

j=1

This naturally leads to an algorithm listed as Algorithm 1. The running time
of the algorithm is O(k(m+n)). The correctness of the values Tv [i], for 1 ≤ i ≤ k
and for each v ∈ V \ S, implies the correctness of the algorithm. The following
theorem is proved by induction on the size of the subtrees.
Theorem 12. Algorithm 1 correctly computes the values Tv [i] for every v ∈
V \ S and 1 ≤ i ≤ k.
Proof. We prove the theorem by using induction on the size of the subtrees. For a
leaf vertex v, the algorithm correctly computes the values Tv [i] for 1 ≤ i ≤ k. For
a non-leaf vertex v, let u1 , u2 , . . . , ud be the children of v in V \S. By induction, all
the k values associated with each child uj of v are correctly computed. Moreover,
Tv [i] is the sum of two quantities (see Equation 4), the first quantity is correct
because it is the sum of the weights of the happy edges from v to S. If Tv [i] is
not correct, it will contradict the correctness of Tuj [∗] for some child uj of v. So,
the second term in the Tv [i] is correct. Hence, the algorithm correctly computes
the values Tv [i] for every v in V \ S and 1 ≤ i ≤ k.
t
u
10

Algorithm 1 Algorithm for a special case of Weighted k-MHE
Input: A weighted undirected graph G with S ⊆ V precolored vertices under a partial
vertex-coloring c : V → [k], V \ S induces a tree, and a vertex r ∈ V \ S as the root
of the tree.
Output: Maximum total weight of the happy edges in G.
1: Mp ← 0
2: for each happy edge uv in the precoloring do
3:
Mp ← Mp + w(uv)
4: end for
5: for each v ∈ V \ S in post-order do
6:
if v is a leaf vertex in V \ S then
7:
for i = 1 to k do
8:
Tv [i] ← 0
9:
for each vu ∈ E such that u ∈ S and c(u) = i do
10:
Tv [i] ← Tv [i] + w(vu)
11:
end for
12:
end for
13:
else
14:
for i = 1 to k do
15:
Tv [i] ← 0
16:
for each vu ∈ E such that u ∈ S and c(u) = i do
17:
Tv [i] ← Tv [i] + w(vu)
18:
end for
19:
for each child u of v in V \ S do
20:
Tv [i] ← Tv [i] + max{(w(vu) + Tu [i]), Tu [ı]}
21:
end for
22:
end for
23:
end if
24: end for
25: return (Mp + Tr [∗])

5.2

Reduction rules combined with the algorithm: a kernel

In this subsection, we assume the edge weights of the Weighted k-MHE instance are positive integers. The kernel will also work for real weights that are
at least 1. We present the following simple reduction rules.
Rule 1 If G contains an isolated vertex, delete it.
Rule 2 If both endpoints of an edge uv ∈ E are colored, remove uv. Furthermore, if c(u) = c(v), decrement ` by the weight on uv.
Proof. As both endpoints of uv are colored, the existence of the edge uv does
not further contribute to the value of the optimal solution. Moreover, if the edge
is already happy under c, we can safely decrement `.
t
u
Rule 3 Contract every color class Ci induced by the partial coloring c into a
single vertex. Let e1 , . . . , er be the (parallel) edges between two vertices u and v.
11

Delete each edge in e1 , . . . , er except for e1 , and update w(e1 ) = w(e1 ) + w(e2 ) +
· · · + w(er ).
Proof. Let G0 be the resulting graph after the application of Rule 3. Because
Rule 2 does not apply, each color class Ci forms an independent set. Thus, G0
contains no self-loops.
Fix a color i, and consider an uncolored vertex v ∈ V \ Ci . Denote by Ni (v)
the neighbors of v with color i, and denote by E[X, Y ] the set of edges whose
one endpoint is in X and the other in Y . Depending on the color v gets in an
extended full coloring of c, either all edges in E[{v}, Ni (v)] are happy or all are
unhappy. Hence, we can safely replace these edges with a single weighted edge.
t
u
Theorem 13. The problem Weighted k-MHE admits a kernel on k + ` vertices.
Proof. Let (G, c, w, `) be a reduced instance of Weighted k-MHE. We claim
that if G has more than k + ` vertices, then we have YES-instance. The proof
follows by the claims below.
Claim 13.1. The weight of each edge is at most `.
Proof. If an edge uv has w(uv) ≥ ` and at least one of u and v is uncolored, we
make uv happy and output YES. On the other hand, any unhappy edge (with
any weight) has been removed by Rule 2.

Claim 13.2. The number of precolored vertices in G is at most k.
Proof. Follows directly from Rule 3.



Claim 13.3. The number of uncolored vertices in G is at most ` − 1.
Proof. Let H be the graph induced by the uncolored vertices, i.e., H = G[V \
∪i∈[k] Ci ]. We note the following two cases:
– If any of the connected components of H is a tree, then we apply the procedure described in Sction 5.1 for that component, and decrement the parameter ` accordingly.
– If w(E(H)) ≥ `, then we color all the vertices in H by the same color making
all the edges in H happy. So the case where w(E(H)) ≥ ` is a YES-instance.
After the application of the above, every component of H contains a cycle, and
|E(H)| < `. So in each component of H, the number of vertices is at most
the number of edges. Consequently, we have |V (H)| ≤ |E(H)| < `. Hence the
number of uncolored vertices is at most ` − 1.

Clearly, all of the mentioned rules can be implemented to run in polynomial
time. Moreover, as we have bounded the number of precolored and uncolored
vertices, the claimed kernel follows.
t
u
12

By combining Theorem 13 with Theorem 11, we have the following corollary.
Corollary 14. For every k ≥ 3, k-MHE can be solved in time O∗ (2` ). For
the special case of k = 3, the problem admits an algorithm running in time
O∗ (1.89` ).

6

Structural parameterization: density and sparsity

In this section we consider the happy coloring problems on sparse and dense
graphs through a structural parameterization.
We begin by recalling a widely known measure for graph sparsity. A tree
decomposition of G is a pair (T, {Xi : i ∈ I}) where Xi ⊆ V , i ∈ I, and T is a
tree with elements of I as nodes such that:
1. for each edge uv ∈ E, there is an i ∈ I such that {u, v} ⊆ Xi , and
2. for each vertex v ∈ V , T [{ i ∈ I | v ∈ Xi }] is a (connected) tree with at least
one node.
The width of a tree decomposition is maxi∈I |Xi | − 1. The treewidth [15] of G is
the minimum width taken over all tree decompositions of G and it is denoted by
tw(G). For algorithmic purposes, it is convenient to consider the following nice
tree decomposition of a decomposition (T, {Xi : i ∈ I}) where every node i ∈ I
is one of the following types:
1. Leaf: node i is a leaf of T and |Xi | = 1.
2. Introduce: node i has exactly one child j and there is a vertex v ∈ V with
Xi = Xj ∪ {v}.
3. Forget: node i has exactly one child j and there is a vertex v ∈ V with
Xj = Xi ∪ {v}.
4. Join: node i has exactly two children j1 and j2 and Xi = Xj1 = Xj2 .
Every n-vertex graph G has a nice tree decomposition with O(n) nodes and
width equal to tw(G). Moreover, such a decomposition can be found in linear
time if tw(G) is bounded (see e.g., [16]).
To show both weighted variants of happy coloring are tractable for bounded
treewidth graphs, we proceed with a standard application of dynamic programming over a tree decomposition. For more details, we refer the reader to [17].
Theorem 15. For any k ≥ 1, both Weighted k-MHE and Weighted kMHV can be solved in time k t · nO(1) , where n is the number of vertices of the
input graph and t is its treewidth.
Proof. Let us prove the statement for Weighted k-MHE, and then explain
how the proof extends for Weighted k-MHV. Let (G, c, w, `) be an instance of
Weighted k-MHE, let ({Xi | i ∈ I}, T = (I, F )) be a nice tree decomposition
of G of width t, and
S let r be the root of T . Moreover, denote by Gi the subgraph
of G induced by j Xj where j belongs to the subtree of T rooted at i.
13

For every node i of T we set up a table Ki indexed by all possible extended
full k-colorings of Xi . Intuitively, an entry of Ki indexed by f : Xi → [k] gives
the total weight of edges happy in Gi under f . It holds that an optimal solution is
given by maxf {Kr [f ]}. In what follows, we detail the construction of the tables
Ki for every node i. The algorithm processes the nodes of T in a post-order
manner, so when processing i, a table has been computed for all children of i.
– Leaf node. Let i be a leaf node and Xi = {v}. Obviously, Gi is edge-free,
so we have Ki [f ] = 0. As k is fixed, Ki is computed in constant time.
– Introduce node. Let i be an introduce node with child j such that Xi =
Xj ∪ {v}. Put differently, Gi is formed from Gj by adding v and a number
of edges from v to vertices in Xj . The properties of a tree decomposition
guarantee that v ∈
/ V (Gj ), and that v is not adjacent to a vertex
in V (Gj ) \
P
Xj . It is not difficult to see that we set Ki [f ] = Ki [f |Xj ] + p∈Nh (v) w(pv),
where Nh (v) denotes the neighbors of v colored with the same color as v. It
follows Ki can be computed in time O(k t+1 ).
– Forget node. Let i be a forget node with child j such that Xi = Xj \ {v}.
Observe that the graphs Gi and Gj are the same. Thus, we set Ki [f ] to the
maximum of Kj [f 0 ] where f 0 |Xi = f . Since there are at most k such colorings
f 0 for each f , we compute Ki in time O(k t+2 ).
– Join node. Let i be a join node with children j1 and j2 such that Xi =
Xj1 = Xj2 . The properties of a tree decomposition guarantee that V (Gj1 ) ∩
V (Gj2 ) = Xi , and that no vertex in V (Gj1 ) \ Xi is adjacent to a vertex in
V (Gj2 ) \ Xi . Thus, we add together weights of happy edges that appear in
Gj1 and Gj2 , while subtracting a term guaranteeing we do not add weights
of edges that are happy in both subgraphs. Indeed, we set Ki [f ] = Kj1 [f ] +
Kj2 [f ] − q, where q is the total weight of the edges made happy under f
in Xi . The table Ki [f ] can also be computed in time O(k t+2 ).
To summarize, each table Ki has size bounded by k t+1 . Moreover, as each table
is computed in O(k t+2 ) time, the algorithm runs in k t · nO(1) time, which is what
we wanted to show.
The proof is similar for Weighted k-MHV, but each table now stores the
total weight of the happy vertices under an extended full k-coloring. In addition,
for each vertex v in a bag, we also store a bit indicating whether or not all
forgotten neighbors of v share its color, i.e., whether v can still be made happy.
t
u
The polynomial-time solvability of a problem on bounded treewidth graphs
implies the existence of a polynomial-time algorithm also for other structural
parameters that are polynomially upper-bounded in treewidth. For instance,
one such parameter is the vertex cover number, i.e., the size of a smallest vertex
cover that a graph has. However, graphs with bounded vertex cover number are
highly restricted, and it is natural to look for less restricting parameters that
generalize vertex cover (like treewidth). Another parameter generalizing vertex
cover is neighborhood diversity, introduced by Lampis [18]. Let us first define the
parameter, and then discuss its connection to both vertex cover and treewidth.
14

Q1

C1

Q2

C2

...

...
X1

X2

Fig. 2: A set of a type partition, where each vertex in Q1 ∪ Q2 has the same type.
The dashed edges appear exactly when Q1 ∪ Q2 induces a clique. The set Q1
forms a complete bipartite graph with both X1 and X2 ; likewise for Q2 (edges
omitted for brevity).
Definition 16. In an undirected graph G, two vertices u and v have the same
type if and only if N (u) \ {v} = N (v) \ {u}.
Definition 17 (Neighborhood diversity [18]). A graph G has neighborhood
diversity t if there exists a partition of V (G) into t sets P1 , P2 , . . . , Pt such that
all the vertices in each set have the same type. Such a partition is called a type
partition. Moreover, it can be computed in linear time.
Note that all the vertices in Pi for every i ∈ [t] have the same neighborhood
in G. Moreover, each Pi either forms a clique or an independent set in G.
Neighborhood diversity can be viewed as representing the simplest of dense
graphs. If a graph has vertex cover number d, then the neighborhood diversity
of the graph is not more than 2d + d (for a proof, see [18]). Hence, graphs
with bounded vertex cover number also have bounded neighborhood diversity.
However, the opposite is not true since complete graphs have neighborhood
diversity 1. Paths and complete graphs also show that neighborhood diversity is
incomparable with treewidth. In general, some NP-hard problems (some of which
remain hard for treewidth), are rendered tractable for bounded neighborhood
diversity (see e.g., [19,20,21]).
We proceed to present algorithms for k-MHE and k-MHV for graphs of
bounded neighborhood diversity. Consider a type partition of a graph G with t
sets, and an instance of I = (G, c, `) of k-MHE. If a set contains both precolored
and uncolored vertices, we split the set into two sets: one containing precisely the
precolored vertices and the other precisely the uncolored vertices. After splitting
each set, the number of sets is at most 2t. For convenience, we say a set is
uncolored if each vertex in it is uncolored; otherwise the set is precolored. Let
the uncolored sets be P1 , P2 , . . . , Pt . In what follows, we discuss how vertices in
these sets are colored in an optimal solution. We say a set is monochromatic if
all of its vertices have the same color.
Lemma 18. There is an optimal extended full coloring for an instance I of
k-MHE such that each uncolored set Pi for 1 ≤ i ≤ t is monochromatic.
15

Proof. Consider any optimal extended full coloring for an instance I. Suppose
the vertices in a set Pi belong to more than one color class. Let Q1 and Q2 be
the (disjoint and non-empty) sets of vertices of Pi belonging to color classes C1
and C2 , respectively. Let X1 and X2 be the neighbors of the vertices in Q1 and
Q2 in color classes C1 and C2 , respectively, as shown in Figure 2. Without loss of
generality, let us assume that |X1 | ≤ |X2 |. By recoloring vertices in Q1 with the
color of C2 , we retain an optimal solution without disturbing the colors of other
vertices. If |E(Q1 , Q2 )| is the number of edges between Q1 and Q2 , the gain in
the number of happy edges by recoloring Q1 is |E(Q1 , Q2 )| + |Q1 |(|X2 | − |X1 |),
which is strictly positive if Pi is a clique and non-negative if Pi is an independent
set.
In conclusion, we have shown that every optimal extended full coloring makes
each Pi inducing a clique monochromatic. Moreover, there is an optimal extended
full coloring making each Pi inducing an independent set monochromatic.
t
u
Theorem 19. For any k ≥ 1, k-MHE can be solved in time O∗ (2t ), where t is
the neighborhood diversity of the input graph.
Proof. First we construct a weighted graph H from G as follows: merge each
uncolored set into a single vertex. Within a precolored set (i.e., a set that is not
uncolored), merge vertices of the same color. This merging operation may create
parallel edges and self-loops in H. Discard all self-loops in H. Replace all parallel
edges with a single weighted edge with weight equivalent to the number edges
between the corresponding vertices. Edges between the vertices in G that are
merged to the same vertex are treated as happy, as there is an optimal extended
full coloring where the merged vertices are colored the same by Lemma 18.
Clearly, H has at most t + kt vertices in which t vertices are uncolored.
Now, k-MHE on G is converted to an instance of Weighted k-MHE on H.
By using Theorem 11, we can solve the instance of k-MHE on G in time O∗ (2t ).
t
u
Using arguments similar to Lemma 18 we can state the following lemma.
This time, let I = (G, c, `) be an instance of k-MHV.
Lemma 20. There is an optimal extended full coloring for an instance I of
k-MHV such that each uncolored set Pi for 1 ≤ i ≤ t is monochromatic.
Proof. Consider any optimal extended full coloring for an instance I. Suppose
the vertices in a set Pi belong to more than one color class. Let Q1 and Q2 be
the (disjoint and non-empty) sets of vertices of Pi belonging to color classes C1
and C2 , respectively. Let X1 and X2 be the neighbors of the vertices in Q1 and
Q2 in color classes C1 and C2 , respectively, as shown in Figure 2. Without loss
of generality, let us assume that |X1 | ≤ |X2 |. By recoloring Q1 with the color
of C2 , we get an optimal solution as well without disturbing the colors of other
vertices. The gain in the number of happy vertices by recoloring Q1 is at most
|X2 | ≥ 0. This proves that there is an optimal extended full coloring where each
set Pi is monochromatic.
t
u
16

Using a construction similar to Theorem 19 we prove the following theorem.
Theorem 21. For any k ≥ 1, k-MHV can be solved in time O∗ (2t ), where t is
the neighborhood diversity of the input graph.
Proof. First we construct a weighted graph H from G as follows: merge each
uncolored set into a single vertex. Within a precolored set, merge vertices of
same color. We assign a weight for each vertex of H equivalent to the number
of vertices in G that are merged to the vertex in H. To make H simple, discard
all parallel edges and self-loops. Clearly, H has at most t + kt vertices in which t
vertices are uncolored.
Now, k-MHV on G is converted to an instance of Weighted k-MHV on H.
By using Theorem 11, we can solve the k-MHV on G in time O∗ (2t ).
t
u

7

Conclusions

We further studied the algorithmic aspects of homophily in networks. As explained, the positive results for Weighted k-MHE also imply tractability results for Multiway Cut, a problem studied by Langberg et al. [7]. Furthermore,
our work invites for a more systematic study of the complexity of happy coloring
for various structural parameters. From a parameterized perspective, an obvious
open question is whether Weighted k-MHV (or even its unweighted variant)
admits a polynomial kernel. We believe the answer is positive, and leave this for
further work.

References
1. Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a
Highly Connected World. Cambridge University Press (2010)
2. McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a Feather: Homophily in
Social Networks. Annual Review of Sociology 27(1) (2001) 415–444
3. Lazarsfeld, P.F., Merton, R.K.: Friendship as a social process: A substantive and
methodological analysis. Freedom and Control in Modern Society 18(1) (1954)
18–66
4. Zhang, P., Li, A.: Algorithmic aspects of homophyly of networks. Theoretical
Computer Science 593 (2015) 117–131
5. Zhang, P., Jiang, T., Li, A.: Improved Approximation Algorithms for the Maximum
Happy Vertices and Edges Problems. In: Proceedings of the 21st Annual International Conference on Computing and Combinatorics (COCOON 2015), Beijing,
China, August 4–6. (2015) 159–170
6. Aravind, N.R., Kalyanasundaram, S., Kare, A.S.: Linear time algorithms for happy
vertex coloring problems for trees. In: Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), Helsinki, Finland, August 17–
19. (2016) 281–292
7. Langberg, M., Rabani, Y., Swamy, C.: Approximation algorithms for graph homomorphism problems. In: Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation (APPROX-RANDOM
2006), Barcelona, Spain, August 28–30. (2006) 176–187

17

8. Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis,
M.: The complexity of multiway cuts (extended abstract). In: Proceedings of the
24th Annual ACM Symposium on Theory of Computing (STOC 1992), Victoria,
British Columbia, Canada, May 4–6. (1992) 241–251
9. Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21(1) (1991)
51–89
10. Cao, Y., Chen, J., Fan, J.H.: An O∗ (1.84k ) parameterized algorithm for the multiterminal cut problem. Information Processing Letters 114(4) (2014) 167–173
11. Diestel, R.: Graph Theory. Springer-Verlag Heidelberg (2005)
12. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M.,
Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
13. Björklund, A., Husfeldt, T., Koivisto, M.: Set Partitioning via Inclusion-Exclusion.
SIAM Journal on Computing 39(2) (2009) 546–563
14. Fomin, F.V., Kratsch, D.: Exact exponential algorithms. Springer Science &
Business Media (2010)
15. Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width.
Journal of Algorithms 7(3) (1986) 309–322
16. Bodlaender, H.L.: A Linear-Time Algorithm for Finding Tree-Decompositions of
Small Treewidth. SIAM Journal on Computing 25(6) (1996) 1305/–1317
17. Bodlaender, H.L., Koster, A.M.: Combinatorial optimization on graphs of bounded
treewidth. The Computer Journal 51(3) (2008) 255–269
18. Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica
64(1) (2012) 19–37
19. Ganian, R.: Using neighborhood diversity to solve hard problems. CoRR
abs/1201.3091 (2012)
20. Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theoretical Computer Science 566 (2015) 39–49
21. Fiala, J., Gavenčiak, T., Knop, D., Koutecký, M., Kratochvı́l, J.: Fixed Parameter
Complexity of Distance Constrained Labeling and Uniform Channel Assignment
Problems. In Dinh, T.N., Thai, M.T., eds.: Proceedings of the 22nd International
Confence on Computing and Combinatorics (COCOON 2016), Ho Chi Minh City,
Vietnam, August 2–4. (2016) 67–78

18

