Inapproximability of treewidth and related problems

DOI10.1613/JAIR.4030MaRDI QIDQ5408191zbMATH OpenOpenAlexWikidataFDO

Authors Yu Wu, Per Austrin, Toniann Pitassi, David Liu

Publication date 9 April 2014

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.4030

Mathematics Subject Classification ID

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

Recommendations

• Inapproximability of treewidth, one-shot pebbling, and related layout problems
• Treewidth and the Computational Complexity of MAP Approximations
• Approximation algorithms for treewidth
• Tree-width and the computational complexity of MAP approximations in Bayesian networks
• The necessity of bounded treewidth for efficient inference in Bayesian networks

Cited in

(23)

• Scheduling series-parallel task graphs to minimize peak memory
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• On the complexity of computing treebreadth
• On the tractability of ( k , i )-coloring
• Minimum fill-in: inapproximability and almost tight lower bounds
• Local tree-width, excluded minors, and approximation algorithms
• Inapproximability and approximability of maximal tree routing and coloring
• On treewidth approximations
• On the complexity of computing treebreadth
• The necessity of bounded treewidth for efficient inference in Bayesian networks
• Inapproximability of treewidth, one-shot pebbling, and related layout problems
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Computing Tree Decompositions
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• An improved parameterized algorithm for treewidth
• On the width of complicated JSJ decompositions
• Treewidth is NP-complete on cubic graphs
• New lower bounds on the cutwidth of graphs
• Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
• Exact and heuristic computation of the scanwidth of directed acyclic graphs
• On the effectiveness of the incremental approach to minimal chordal edge modification

This page was built for publication: Inapproximability of treewidth and related problems

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