Some Probabilistic Results on Width Measures of Graphs

Jakub MarečekarXiv 2009 · DOI · arXiv

Abstract

Fixed parameter tractable (FPT) algorithms run in time $f(p(x)) \text{poly}(|x|)$, where $f$ is an arbitrary function of some parameter $p$ of the input $x$ and poly is some polynomial function. Treewidth, branchwidth, cliquewidth, NLC-width, rankwidth, and booleanwidth are parameters often used in the design and analysis of such algorithms for problems on graphs. We show asymptotically almost surely (aas), there are $\Omega(n)$ lower bounds on the treewidth, branchwidth, cliquewidth, NLC-width, and rankwidth of graphs drawn from a simple random model. This raises important questions about the generality of FPT algorithms using the corresponding decompositions.

Introduction

In theoretical computer science, many NP-hard graph problems are considered computationally intractable for general inputs. However, the framework of Fixed Parameter Tractability (FPT) provides a pathway to efficiency by focusing on specific structural properties. If a graph's "simplicity"—quantified by parameters known as width measures—is low, algorithms can solve these problems in polynomial time relative to the number of vertices, even if the overall problem is NP-hard.

Various measures have been developed to capture this structural simplicity, including treewidth, branchwidth, cliquewidth, rankwidth, and booleanwidth. While these measures have enabled the creation of powerful dynamic programming algorithms, a fundamental question remains: how common are graphs with low width? This paper investigates the probabilistic behavior of these measures in random graphs to determine the practical scope of FPT algorithms.

Methodology

The research utilizes probabilistic methods to analyze width measures, primarily focusing on the Erdős–Rényi random graph model $G(n, 1/2)$ and random matrices over finite fields.

  1. Random Matrix Analysis: The author first examines random $m \times n$ matrices over the finite field $GF(2)$. Using tools from random matrix theory, the paper establishes a lemma showing that the minimum rank of certain submatrices is bounded from below by $\Omega(n)$ asymptotically almost surely (aas).
  2. Linking Rank to Graph Width: The author connects these matrix properties to graph theory by utilizing the minimax theorem of Robertson and Seymour (relating branchwidth to "tangles") and Oum’s work on rankwidth. This demonstrates that the rank of a graph's adjacency matrix directly dictates its structural width measures.
  3. Inequality Chains: After establishing a lower bound for rankwidth, the author uses a series of known mathematical inequalities to propagate this result to other measures, including treewidth, branchwidth, cliquewidth, and NLC-width.

Key Insights and Results

The Complexity of the "Average" Graph

The most significant finding is that for a typical random graph, width measures are not small; they grow linearly with the number of vertices. Specifically, for a graph drawn from $G(n, 1/2)$, the following measures are $\Theta(n)$ asymptotically almost surely:

  • Rankwidth
  • Treewidth
  • Branchwidth
  • Cliquewidth
  • NLC-width

Because these measures are trivially upper-bounded by $n$, the $\Omega(n)$ lower bound proves that these measures are exactly $\Theta(n)$ for random graphs. This suggests that the structural "simplicity" required for FPT algorithms is a rare property in dense random graphs.

The FPT Bottleneck

FPT algorithms typically feature a runtime of $f(p) \cdot \text{poly}(n)$, where $p$ is the width parameter. In many cases, $f$ is an exponential function. If $p$ is $\Omega(n)$, the $f(p)$ term becomes $f(n)$, effectively transforming the "efficient" FPT algorithm back into a standard exponential-time algorithm. This highlights a major limitation: decomposition-based methods may not provide a computational advantage for average-case instances in these models.

Booleanwidth Bounds

The paper provides a new theoretical bound for booleanwidth ($\beta w(G)$), establishing that $\beta w(G) = O(rw(G) \log rw(G))$ aas. This result helps clarify the relationship between booleanwidth and the more established rankwidth measure.

Conclusion and Future Directions

This research establishes that many popular width measures are large for dense random graphs, which poses a challenge to the perceived generality of FPT algorithms. However, the author identifies several areas for further exploration:

  • Sparse Graph Models: Future research should investigate whether these width measures remain linear in sparse random models (where edge density is significantly lower) or if they drop to more manageable logarithmic scales ($O(\log n)$).
  • Characterizing "Easy" Instances: There is a continued need to identify which specific classes of graphs naturally possess low width, as these are the instances where FPT algorithms are truly effective.
  • Integer Programming: The author suggests investigating whether the constraint matrices of large-scale integer programs exhibit low branchwidth or rankwidth, which could lead to new polynomial-time solutions for specific NP-hard optimization problems.

Summary updated

Abstract

Fixed parameter tractable (FPT) algorithms run in time f(p(x)) poly(|x|), where f is an arbitrary function of some parameter p of the input x and poly is some polynomial function. Treewidth, branchwidth, cliquewidth, NLC-width, rankwidth, and booleanwidth are parameters often used in the design and analysis of such algorithms for problems on graphs. We show asymptotically almost surely (aas), there are Omega(n) lower bounds on the treewidth, branchwidth, cliquewidth, NLC-width, and rankwidth of graphs drawn from a simple random model. This raises important questions about the generality of FPT algorithms using the corresponding decompositions.
BibTeX
@misc{marecek2009some,
  author = {Jakub Mareček},
  title = {{Some Probabilistic Results on Width Measures of Graphs}},
  year = {2009},
  eprint = {0908.1772},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0908.1772},
}
Figure