Lower bounds for the happy coloring problems

DOI10.1016/j.tcs.2020.06.005zbMath1453.68126arXiv1906.05422OpenAlexW4206097482MaRDI QIDQ5918935

Danil Sagunov, Ivan A. Bliznets

Publication date: 1 September 2020

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.05422

zbMATH Keywords

parameterized complexityexponential time hypothesiskernelizationmaximum happy edgesmaximum happy verticeshappy coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Parameterized complexity of happy coloring problems ⋮ New algorithms for a simple measure of network partitioning ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithmic aspects of homophyly of networks
• Strong computational lower bounds via parameterized complexity
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• Finding happiness: an analysis of the maximum happy vertices problem
• On structural parameterizations of happy coloring, empire coloring and boxicity
• On the parameterized complexity of happy vertex coloring
• The parameterized complexity of happy colorings
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Kernelization for maximum happy vertices problem
• Tight lower bounds for certain parameterized NP-hard problems
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
• The Complexity of Multiterminal Cuts
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Kernelization Lower Bounds Through Colors and IDs
• On Problems as Hard as CNF-SAT
• Reducibility among Combinatorial Problems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• The complexity of theorem-proving procedures

This page was built for publication: Lower bounds for the happy coloring problems