Lower Bounds for the Happy Coloring Problems

I. Bliznets; Sagunov D.

doi:10.1007/978-3-030-26176-4_41

Publications

?

Lower Bounds for the Happy Coloring Problems

P. 490–502.

Bliznets I., Sagunov D.

In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17. Main focus of our work is lower bounds on the computational complexity of these problems. Established lower bounds can be divided into the following groups: NP-hardness of the above guarantee parameterization, kernelization lower bounds (answering questions of Misra and Reddy ’17), exponential lower bounds under the Set Cover Conjecture and the Exponential Time Hypothesis, and inapproximability results. Moreover, we present an ∗(ℓ𝑘)O∗(ℓk) randomized algorithm for MHV and an ∗(2𝑘)O∗(2k) algorithm for MHE, where ℓℓ is the number of colors used and k is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account.

Language: English

DOI

Keywords: lower bounds Happy coloring

In book

Computing and Combinatorics 25th International Conference, COCOON 2019, Xi'an, China, July 29–31, 2019, Proceedings

Vol. 11653: Lecture Notes in Computer Science. , Springer, 2019.

Lower bounds for the happy coloring problems

Bliznets I., Sagunov D., Theoretical Computer Science 2020 Vol. 838 P. 94–110

Added: October 8, 2020

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

Bliznets I., Lukas M., Cygan M. et al., ACM Transactions on Algorithms 2020 Vol. 16 P. 1–31

In this work, we focus on several completion problems for subclasses of chordal graphs: MINIMUM FILL-IN, INTERVAL COMPLETION, PROPER INTERVAL COMPLETION, TRIVIALLY PERFECT COMPLETION, and THRESHOLD COMPLETION. In these problems, the task is to add at most k edges to a given graph to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all ...

Added: October 8, 2020

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

Bliznets I., Cygan M., Komosa P. et al., ACM Transactions on Algorithms 2020 Vol. 16 No. 2 P. 1–31

Added: July 19, 2020

On Happy Colorings, Cuts, and Structural Parameterizations

Bliznets I., Sagunov D., , in: Graph-Theoretic Concepts in Computer Science 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised PapersVol. 11789: Lecture Notes in Computer Science.: Springer, 2019. P. 148–161.

We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always ...

Added: November 1, 2019

Graph-Theoretic Concepts in Computer Science 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers

Bliznets I., Springer, 2019.

Added: October 29, 2019

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

Bliznets Ivan, Cygan M., Komosa P. et al., , in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms.: SIAM, 2016. P. 1132–1151.

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper IntervalCompletion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds ...

Added: October 31, 2018