Complexity and approximability of the happy set problem

DOI10.1016/J.TCS.2021.03.023MaRDI QIDQ2662689zbMATH OpenOpenAlexFDO

Authors Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Eiji Miyano, Ippei Terabaru, Guohui Lin

Publication date 14 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.03.023

zbMATH Keywords

approximabilitybipartite graphsblock graphscomputational complexitycubic graphsinterval graphsmaximum happy set problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Parameterized algorithms for the happy set problem
• Finding happiness: an analysis of the maximum happy vertices problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation algorithms for vertex happiness

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic aspects of homophyly of networks
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Clustering and domination in perfect graphs
• Complexity of finding dense subgraphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Exact algorithms for problems related to the densest \(k\)-set problem
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Finding happiness: an analysis of the maximum happy vertices problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Networks, crowds and markets. Reasoning about a highly connected world.
• On rigid circuit graphs
• On structural parameterizations of happy coloring, empire coloring and boxicity
• On the parameterized complexity of happy vertex coloring
• On the tree representation of chordal graphs
• Parameterized algorithms for the happy set problem
• Power of Natural Semijoins
• PTAS for densest \(k\)-subgraph in interval graphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The dense \(k\)-subgraph problem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tight complexity bounds for FPT subgraph problems parameterized by the clique-width

Cited in

(9)

• A simple and effective algorithm for the maximum happy vertices problem
• Happy set problem on subclasses of co-comparability graphs
• Approximation algorithms for vertex happiness
• Parameterized algorithms for the happy set problem
• Parameterized algorithms for the happy set problem
• Happy set problem on subclasses of co-comparability graphs
• Corrigendum to: ``Complexity and approximability of the happy set problem
• On \(d\)-stable locally checkable problems parameterized by mim-width
• Happy set problems on cubic graphs and convex bipartite graphs

This page was built for publication: Complexity and approximability of the happy set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662689)