Parameterized complexity of happy coloring problems

Agrawal, Akanksha and Aravind, N.R. and Kalyanasundaram, Subrahmanyam and Kare, Anjeneya Swami and Lauri, Juho and Misra, Neeldhara and Reddy, I. Vinod (2020) Parameterized complexity of happy coloring problems. Theoretical Computer Science, 835. pp. 58-81. ISSN 03043975

Full text not available from this repository. (Request a copy)


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 and an integer ℓ, find an extended full k-coloring of G making at least ℓ edges happy. When we want to make ℓ vertices happy on the same input, the problem is known as MAXIMUM HAPPY VERTICES ( k-MHV ). We perform an extensive study into the complexity of the problems, particularly from a parameterized viewpoint. For every k≥3, we prove both problems can be solved in time 2nnO(1). Moreover, by combining this result with a linear vertex kernel of size (k+ℓ) for k-MHE, we show that the edge-variant can be solved in time 2ℓnO(1). In contrast, we prove that the vertex-variant remains W[1]-hard for the natural parameter ℓ. However, the problem does admit a kernel with O(k2ℓ2) vertices for the combined parameter k+ℓ. From a structural perspective, we show both problems are fixed-parameter tractable for treewidth and neighborhood diversity, which can both be seen as sparsity and density measures of a graph. Finally, we extend the known [Formula presented]-completeness results of the problems by showing they remain hard on bipartite graphs and split graphs. On the positive side, we show the vertex-variant can be solved optimally in polynomial-time for cographs.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Aravind, N R
Item Type: Article
Uncontrolled Keywords: Algorithmic aspects; Bipartite graphs; Coloring problems; Combined parameter; Density measures; Parameterized complexity; Polynomial-time; Positive sides
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 30 Jul 2021 04:13
Last Modified: 07 Mar 2022 06:13
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8568 Statistics for this ePrint Item