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)
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 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.
Actions (login required)
 |
View Item |
Altmetric
Altmetric