Genus characterizes the complexity of certain graph problems: Some tight results

DOI10.1016/j.jcss.2006.11.001zbMath1121.68086OpenAlexW1999211091MaRDI QIDQ2641866

Ge Xia, Eric Sedgwick, Ljubomir Perković, Jian'er Chen, Iyad A. Kanj

Publication date: 23 August 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.11.001

zbMATH Keywords

parameterized computationgraph genuspolynomial time approximation schemesubexponential time computation

Mathematics Subject Classification ID

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

Related Items (9)

Unnamed Item ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Maximum Cut Parameterized by Crossing Number ⋮ A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation ⋮ Unnamed Item ⋮ The genus of the balanced hypercube ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ The complexity of tree partitioning ⋮ Revising Johnson's table for the 21st century

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on approximating graph genus
• Strong computational lower bounds via parameterized complexity
• Efficient bounds for the stable set, vertex cover and set packing problems
• Optimization, approximation, and complexity classes
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Algorithmic graph embeddings
• Which problems have strongly exponential complexity?
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• On the existence of subexponential parameterized algorithms
• Tight lower bounds for certain parameterized NP-hard problems
• A refined search tree technique for dominating set on planar graphs
• Vertex Cover: Further Observations and Further Improvements
• The graph genus problem is NP-complete
• Proof verification and the hardness of approximation problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Polynomial-time data reduction for dominating set
• Applications of a Planar Separator Theorem
• Vertex packings: Structural properties and algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Parameterized complexity: exponential speed-up for planar graph problems
• Automata, Languages and Programming

This page was built for publication: Genus characterizes the complexity of certain graph problems: Some tight results