• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • On Happy Colorings, Cuts, and Structural Parameterizations
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
August 13, 2026
‘Working with AI Solves a Wide Range of Engineering Problems
Artificial intelligence is a working tool based on a balanced combination of algorithms and engineering. Experts and doctoral students from the HSE Moscow Institute of Electronics and Mathematics explain how AI technologies can improve an application, device, or system, and what engineering tasks are solved in the process.
August 12, 2026
‘I Would Like My Research to Help Make the World a Calmer and Better Place
Whatever task Saraa Ali, Junior Research Fellow at the Laboratory of Methods for Big Data Analysis (LAMBDA) of the AI and Digital Science Institute (HSE Faculty of Computer Science), is working on, she thinks about how it can benefit people. She told the Young Scientists of HSE University project about her large family, diagnosing three-phase motors, and her dream of building a children’s home in her native country.
August 11, 2026
‘The Peak of Stupidity and ‘The Valley of Despair: HSE Economists Propose an Explanation for the Dunning–Kruger Effect
The Dunning–Kruger effect, which describes a sharp surge in self-confidence among beginners followed by an equally rapid decline as they gain experience, can be explained by the nature of the learning process and the acquisition of new knowledge. This conclusion was reached by Andrey Vorchik of the HSE Faculty of Economic Sciences together with independent researcher Murat Mamyshev. They developed a mathematical model of learning and demonstrated how subjective confidence is formed and changes as knowledge accumulates, as well as how teachers can reduce the ‘valley of despair’ experienced by learners.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

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 complexityHappy coloringHomophily lawClique-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.
Similar publications
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.
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: 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
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit