Fixed-parameter Tractable Distances to Sparse Graph Classes

Jannis Bulian, Anuj Dawar

Abstract

We show that for various classes $\mathcal{C}$ of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph $G$ to $\mathcal{C}$ is fixed-parameter tractable (FPT). The results are based on two general techniques. The first of these, building on recent work of Grohe et al., establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order (FO) definable is FPT. The second shows that determining the elimination distance of a graph $G$ to a minor-closed class $\mathcal{C}$ is FPT.

Introduction

In algorithmic graph theory, many problems that are computationally intractable (NP-hard) on general graphs become efficiently solvable when restricted to specific graph classes, such as trees, planar graphs, or graphs of bounded treewidth. A natural extension of this observation is to consider graphs that are "close" to such classes. If a graph $G$ can be transformed into a member of a "nice" class $\mathcal{C}$ by removing a small number of vertices or edges, we might still be able to solve complex problems on $G$ efficiently.

However, a significant bottleneck exists: calculating the distance from $G$ to $\mathcal{C}$ is itself often an NP-hard problem. For instance, finding the minimum number of vertices to delete to make a graph edge-less is equivalent to the Vertex Cover problem. This paper investigates the parameterized complexity of such distance measures, specifically focusing on whether these problems are Fixed-Parameter Tractable (FPT) when the distance $k$ is the parameter.

Theoretical Frameworks

1. The FO-Definability Approach

The authors first leverage algorithmic meta-theorems, which provide general conditions under which problems are FPT. A landmark result by Grohe, Kreutzer, and Siebertz established that evaluating First-Order (FO) logic formulas is FPT on "nowhere dense" graph classes—a very broad category of sparse graphs.

The authors extend this by introducing the concept of slicewise properties. A property is slicewise nowhere dense if, for every fixed $k$, the class of graphs possessing that property (e.g., being at distance $k$ from $\mathcal{C}$) is nowhere dense. They prove that if a graph class $\mathcal{C}$ is nowhere dense and the distance measure is FO-definable, then determining if a graph is at distance $k$ from $\mathcal{C}$ is FPT. This covers common measures like vertex deletion, edge deletion, and edge addition.

2. Elimination Distance and Minor-Closed Classes

The second approach addresses "minor-closed" classes, such as planar graphs or graphs with bounded genus. These classes are characterized by the Robertson-Seymour Theorem, which states they can be defined by a finite set of forbidden minors.

The authors focus on elimination distance, a recursive measure of distance. To have an elimination distance of $k$ to a class $\mathcal{C}$, one must be able to remove a vertex from every connected component of the graph such that the remaining components have an elimination distance of $k-1$ to $\mathcal{C}$. This is a generalization of the concept of tree-depth. The paper demonstrates that for any minor-closed class $\mathcal{C}$, the class of graphs with elimination distance $k$ to $\mathcal{C}$ is also minor-closed. By algorithmically identifying the forbidden minors for these expanded classes, the authors prove that computing elimination distance to any minor-closed class is FPT.

Key Insights

  • Generality of Nowhere Dense Classes: The research reinforces that "nowhere dense" is a robust boundary for tractability. Many distance problems that are hard on dense graphs become manageable here.
  • Recursive Structure: The proof for elimination distance relies on an inductive construction. By showing that the "closure" of a minor-closed class under disjoint unions and the addition of "apex" vertices (vertices connected to all others) remains minor-closed, the authors provide a pathway to handle recursive distance measures.
  • Tree-depth: As a corollary, the paper provides a new logic-based proof that determining if a graph has tree-depth $k$ is FPT, simplifying previous approaches.

Conclusion and Future Work

This work provides a powerful toolkit for classifying the complexity of graph distance problems. It successfully answers the open question regarding the tractability of elimination distance to minor-closed classes.

However, limitations remain. The first method requires FO-definability, which excludes certain minor-closed properties (like being acyclic). Furthermore, the "hidden constants" in the FPT running times—often involving towers of exponentials—mean these algorithms are currently of theoretical interest rather than practical tools for large-scale industrial applications. A specific remaining challenge is determining the elimination distance to the class of graphs with a maximum degree $d$, which does not fit neatly into the FO-definable or minor-closed frameworks for $d > 0$.

Summary updated

Abstract

We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.
BibTeX
@inproceedings{bulian2017fixed,
  author = {Jannis Bulian and Anuj Dawar},
  title = {{Fixed-parameter Tractable Distances to Sparse Graph Classes}},
  booktitle = {Algorithmica},
  year = {2017},
  url = {https://openreview.net/forum?id=9WdrHqj8qv},
}

Loading related content...

Figure