Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
2012 (English)In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, 13-24 p.Conference paper (Refereed)
We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, one-shot black (and black-white) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as minimum cut linear arrangement and interval graph completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are hard to approximate within any constant factor.
Place, publisher, year, edition, pages
2012. 13-24 p.
IdentifiersURN: urn:nbn:se:kth:diva-112871DOI: 10.1007/978-3-642-32512-0_2ScopusID: 2-s2.0-84865297320OAI: oai:DiVA.org:kth-112871DiVA: diva2:587539
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012; Cambridge, MA; United States
QC 201305232013-01-142013-01-142016-04-21Bibliographically approved