• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Lower Bounds for the Happy Coloring Problems
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 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
September 17, 2026
'I Wish That People Would Place Greater Trust in Science'
When Tatiana Eremicheva chose Fundamental and Computational Linguistics as her field of study, she thought it would be about learning languages. Instead, she discovered it was about helping people. In this interview for the HSE Young Scientists project, she discusses science as a way of understanding the world, billiards as a team-building activity, and why learning to read is not always as easy as it seems.
September 15, 2026
Immunity to Chaos: How Personal Resources Help Us Cope with the Challenges of a Turbulent World
International conflicts, crises and digital overload—the modern world puts our minds to the test every day. Traditional psychology often focuses on the consequences: anxiety, depression, and psychosomatic disorders. But what if we looked at the problem differently—through the lens of the resources that prevent us from breaking down? Psychological immunity is precisely this set of resources. Alena Zolotareva and her group, Psychological Immunity as a Resource for Positive Functioning, are developing an integrative model of this phenomenon, adapting diagnostic tools and preparing for large-scale empirical research. Why do psychologists need to collaborate with medical professionals, and how could their research transform preventive care in clinics and corporations?
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.

 

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

?

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 boundsHappy 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.
Similar publications
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 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
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: 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.
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
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
  • 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