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. 5881.
ISSN 03043975
Full text not available from this repository.
(
Request a copy)
Abstract
In a vertexcolored 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 ( kMHE ) problem: given a partially kcolored graph G and an integer ℓ, find an extended full kcoloring 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 ( kMHV ). 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 kMHE, we show that the edgevariant can be solved in time 2ℓnO(1). In contrast, we prove that the vertexvariant 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 fixedparameter 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 vertexvariant can be solved optimally in polynomialtime for cographs.
[error in script]
Actions (login required)

View Item 