Inapproximability of Treewidth and Related Problems

Yu Ledell Wu, Per Austrin, Toniann Pitassi, David LiuJAIR 2014 · OpenReview

TL;DR

This paper proves that several fundamental graph problems, including Treewidth, Pathwidth, and Minimum Fill-In, are NP-hard to approximate within any constant factor. This is a significant result because these problems are crucial for efficient inference in graphical models and various other computational tasks. The hardness is established under the recently proposed Small Set Expansion (SSE) conjecture, a strong variant of the Unique Games Conjecture.

What Problem Does This Paper Address?

Many problems in artificial intelligence and machine learning, particularly those involving graphical models like Bayesian Networks and Markov Networks, become tractable on graphs with bounded Treewidth. This makes finding or approximating the Treewidth of a graph a fundamental problem. While algorithms exist that are efficient for graphs with small Treewidth, they rely on having a good tree decomposition. Computing the exact Treewidth is NP-hard, and existing approximation algorithms have limitations. A key open question was whether constant-factor approximation algorithms exist for Treewidth and related graph layout problems. This paper aims to resolve this by showing that such algorithms are unlikely to exist, assuming the SSE conjecture.

Methods

The paper's core contribution lies in proving the inapproximability of several graph problems using reductions from the Small Set Expansion (SSE) conjecture. The SSE conjecture is a strong hypothesis in computational complexity theory that implies hardness for problems involving graph expansion properties. The authors first establish hardness for Minimum Linear Arrangement (MLA) and Minimum Cut Linear Arrangement (MCLA) based on the SSE conjecture. They then use these results to derive hardness for a range of directed graph layout problems, including One-Shot Black Pebbling and One-Shot Black-White Pebbling. Finally, they connect these problems to Treewidth and Pathwidth, showing that these too are hard to approximate within a constant factor. The reductions involve constructing new graphs from existing ones, carefully designed to preserve or transform the expansion properties relevant to the SSE conjecture.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness results and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • SSE Conjecture as a Unifying Hardness Hypothesis: The paper highlights the SSE conjecture as a powerful tool for proving hardness of approximation for a broad class of graph problems, particularly those related to graph expansion and connectivity.
  • Bridging Graph Expansion and Graph Layout: A key insight is the connection between the expansion properties of graphs (central to SSE) and the structure of graph layout problems, where ordering vertices is crucial. The reductions effectively translate expansion hardness into layout hardness.
  • Treewidth and Pathwidth are Fundamentally Hard to Approximate: The paper provides the first evidence that constant-factor approximation algorithms for Treewidth and Pathwidth are unlikely to exist, a significant theoretical result with implications for algorithms in AI and machine learning.
  • Unified Hardness for a Family of Problems: The authors demonstrate that a diverse set of graph layout problems, including those related to pebbling and ordering, share a common hardness barrier under the SSE conjecture.

Key Results

The paper proves that the following problems are SSE-hard to approximate within any constant factor:

  • Treewidth
  • Pathwidth
  • Minimum Fill-In
  • One-Shot Black Pebbling
  • One-Shot Black-White Pebbling
  • Minimum Linear Arrangement (MLA)
  • Minimum Cut Linear Arrangement (MCLA)
  • Interval Graph Completion
  • A set of eight related graph layout problems.

These results imply that, unless P=NP, there is no polynomial-time algorithm that can approximate these problems to within a constant factor.

Limitations and Future Work

  • Reliance on SSE Conjecture: The hardness results are contingent on the truth of the Small Set Expansion (SSE) conjecture. While SSE is a strong conjecture, its status is still open, and future work might explore alternative hardness assumptions.
  • Extending to Other Graph Layout Problems: The authors suggest that their results can likely be extended to a wider range of graph layout problems, including those involving different aggregation norms (e.g., $L_p$ norms).
  • Weaker Hardness Assumptions: The paper notes that it would be valuable to obtain hardness results based on weaker assumptions like the Unique Games Conjecture (UGC), as SSE is a stronger hypothesis.
  • Unrestricted Pebbling Problems: The paper mentions that results for unrestricted pebbling problems (which are PSPACE-complete) are largely unknown, and extending their work to these problems is an interesting avenue.
  • Practical Implications: While the theoretical hardness is established, the practical implications for algorithms on specific graph classes or for approximate solutions with larger approximation ratios remain an area for further investigation.

Summary updated

BibTeX
@article{wu2014inapproximability,
  author = {Yu Ledell Wu and Per Austrin and Toniann Pitassi and David Liu},
  title = {{Inapproximability of Treewidth and Related Problems}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=xQ8BOy7JbM},
}
Figure