On Happy Colorings, Cuts, and Structural Parameterizations

Ivan Bliznets, Danil Sagunov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers
EditorsIgnasi Sau, Dimitrios M. Thilikos
PublisherSpringer Nature
Pages148-161
Number of pages14
ISBN (Print)9783030307851
DOIs
StatePublished - 1 Jan 2019
Event45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spain
Duration: 19 Jun 201921 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11789 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019
CountrySpain
CityCatalonia
Period19/06/1921/06/19

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Clique-width
  • Distance to triviality
  • Happy coloring
  • Homophily law
  • Maximum happy edges
  • Maximum happy vertices
  • Multiway cut
  • Parameterized complexity
  • Treewidth

Fingerprint Dive into the research topics of 'On Happy Colorings, Cuts, and Structural Parameterizations'. Together they form a unique fingerprint.

Cite this