On Happy Colorings, Cuts, and Structural Parameterizations

I. Bliznets; Sagunov D.

doi:10.1007/978-3-030-30786-8_12

Publications

?

On Happy Colorings, Cuts, and Structural Parameterizations

P. 148–161.

Bliznets I., Sagunov D.

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 attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

Language: English

DOI

Text on another site

Keywords: parameterized complexity Happy coloring Homophily law Clique-width

In book

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

Bliznets I. Vol. 11789: Lecture Notes in Computer Science. , Springer, 2019.

Algorithms for standard-form ILP problems via Komlós’ discrepancy setting

Gribanov D., Khayaleyev T., Cherniavskii M. et al., , in: ESA'2026: Proceedings of the 34th Annual European Symposium on Algorithms.: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2026. Ch. 388 P. 25:1–25:22.

We study the standard-form ILP problem max{c⊤x:Ax=b,x∈Zn≥0}, where A∈Zk×n has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k×k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κk denote the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. Up to polynomial ...

Added: August 24, 2026

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

Gribanov D., Shumilov I., Malyshev D. et al., Journal of Global Optimization 2024 Vol. 89 P. 1033–1067

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Zn , assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = b, x ≥ 0 with a sparse ...

Added: March 6, 2024

Lower bounds for the happy coloring problems

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

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 '18, Aravind et al. '16, Choudhari and Reddy '18, Misra and Reddy '18. Main focus of our work is lower bounds on the computational complexity ...

Added: October 8, 2020

Lower Bounds for the Happy Coloring Problems

Bliznets I., Sagunov D., , in: Computing and Combinatorics 25th International Conference, COCOON 2019, Xi'an, China, July 29–31, 2019, ProceedingsVol. 11653: Lecture Notes in Computer Science.: Springer, 2019. P. 490–502.

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 ...

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

Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

Bliznets Ivan, Karpov N., , in: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).: [б.и.], 2017. P. 6:1–6:14.

Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model generally clusters are defined as cliques. However, such approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different ...

Added: October 30, 2018

Subexponential Parameterized Algorithm for Interval Completion

Bliznets Ivan, Fomin F., Pilipczuk M. et al., ACM Transactions on Algorithms 2018 Vol. 14 No. 3 P. 1–62

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most kedge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan et al. [FOCS 1994; ...

Added: October 30, 2018

Parameterized Complexity of Superstring Problems

Bliznets Ivan, Fomin F., Golovach P. et al., Algorithmica 2017 Vol. 79 No. 3 P. 798–813

In the Shortest Superstring problem we are given a set of strings S=\{s_1, \ldots , s_n\} and integer \ell and the question is to decide whether there is a superstring s of length at most \ellcontaining all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2^{\mathcal {O}(k)} {\text {poly}}(n) finds a ...

Added: October 29, 2018

Computability and Complexity

Day A., Fellows M., Greenberg N. et al., Berlin: Springer, 2017.

Added: October 26, 2018