Clique-width: When Hard Does Not Mean Impossible

Robert Ganian, Petr Hlinený, Jan Obdrzálek

TL;DR

This paper tackles two notoriously difficult graph problems, Minimum Leaf Out-Branching and Edge Disjoint Paths, on graphs with bounded "clique-width." They introduce a novel XP-time algorithm for the former and surprisingly show the latter is definable in a logical framework, leading to a linear-time FPT algorithm. This work expands the toolkit for solving hard problems on structured graph classes.

What Problem Does This Paper Address?

Many graph problems are NP-hard in general, making them intractable for large inputs. Parameterized complexity offers a way out by focusing on specific graph structures that can be quantified by a "parameter" (like tree-width or clique-width). The goal is to find algorithms whose runtime is exponential only in the parameter, not the input size.

Clique-width is a structural parameter that has gained traction because it captures a broad class of graphs for which many problems become tractable. However, for some problems, even with bounded clique-width, efficient (FPT) algorithms were elusive, or their complexity was unknown. This paper specifically targets two such problems on digraphs (directed graphs) with bounded clique-width:

  1. Minimum Leaf Out-Branching (MINLOB): Given a digraph, find a spanning directed tree (an "out-branching") that minimizes the number of leaves. This problem is known to be W[2]-hard when parameterized by clique-width, meaning a truly efficient FPT algorithm is unlikely unless the Exponential Time Hypothesis fails.
  2. Edge Disjoint Paths: Given a digraph and a set of terminal pairs, find paths between these pairs that do not share any edges. While the undirected version is more manageable, the directed version with a fixed number of paths remained a challenge for clique-width parameterization.

The paper aims to bridge this gap by developing new algorithmic approaches for these problems on clique-width bounded digraphs.

Methods

The paper employs two distinct strategies for the two problems:

  • For Minimum Leaf Out-Branching (MINLOB):
    • The authors introduce a novel XP-time algorithm parameterized by clique-width. This is significant because previous attempts for related problems (like Hamiltonian Path) were either for specific cases or didn't resemble this new approach.
  • The core of the algorithm relies on a dynamic programming approach over the k-expression of the graph (a representation of how the graph can be built using specific operations).
  • Instead of directly tracking exact "signatures" of potential solutions (which proved too complex), they introduce "weak signatures." These are a more relaxed representation of the state of partial solutions during the dynamic programming process.
  • The algorithm computes a set of all possible weak signatures for sub-expressions of the k-expression. A crucial theorem then connects the existence of a specific type of weak signature (one corresponding to a single out-tree with the desired number of leaves) to the existence of a MINLOB solution.
  • For Edge Disjoint Paths:
    • The authors take a surprising logical approach. They show that the existence of a set of k pairwise edge-disjoint paths in a digraph can be expressed using Monadic Second-Order Logic of one-sorted adjacency graphs (MSO₁).
  • This is non-trivial because MSO₁ typically quantifies over vertices and vertex sets, not edges directly. The paper devises a clever "trick" to express edge disjointness indirectly.
  • Once the problem is formulated as an MSO₁ sentence, they leverage existing results (specifically, a linear-time FPT algorithm for MSO₁ definable problems on graphs of bounded clique-width from a related work [3]) to obtain their efficient algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and complexity, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • "Weak Signatures" for MINLOB: The introduction of "weak signatures" is a key algorithmic innovation. It allows for a more manageable dynamic programming state space compared to exact signatures, enabling an XP-time solution for a problem previously considered hard to tackle with standard DP on k-expressions.
  • MSO₁ Definability for Edge Disjoint Paths: The most striking insight is that the edge-disjoint paths problem, which seems inherently about edges, can be expressed in MSO₁ logic. This opens up a new avenue for solving such problems by translating them into a logical framework and then applying existing logical solvers.
  • Bridging the Gap for Hard Problems: The paper demonstrates that even problems known to be W[2]-hard (like MINLOB) can have XP-time algorithms parameterized by clique-width, pushing the boundaries of what's considered "tractable" in parameterized complexity.
  • Clique-width as a Powerful Parameter: The success in tackling these two problems further solidifies clique-width (and its related parameter, rank-width) as a versatile and powerful structural parameter for designing efficient algorithms on graphs.

Key Results

  • Minimum Leaf Out-Branching: An XP-time algorithm is presented for MINLOB on digraphs of clique-width k. The runtime is $O(n \cdot f(k))$, where $f(k)$ is exponential in $k$ (specifically, $2^{O(k)}$ or $2^{O(2^k)}$ depending on the input format). This resolves an open question regarding the parameterized complexity of MINLOB by clique-width.
  • Edge Disjoint Paths: A linear-time FPT algorithm is established for both undirected and directed edge-disjoint paths problems with a fixed number of terminal pairs, parameterized by clique-width. This is achieved by showing the problem's definability in MSO₁ logic.

Limitations and Future Work

  • XP vs. FPT for MINLOB: While the paper provides an XP-time algorithm for MINLOB, it acknowledges that the problem is W[2]-hard, implying that a true FPT algorithm (with a runtime like $f(k) \cdot \text{poly}(n)$) is unlikely unless the Exponential Time Hypothesis is false. The authors suggest that the difference between their XP algorithm and a hypothetical FPT algorithm might warrant further conceptual investigation.
  • Quantifier Alternation Depth for Edge Disjoint Paths: The MSO₁ formula constructed for edge-disjoint paths has a quantifier alternation depth that grows with the number of paths k. The paper poses a question about whether an MSO₁ description with a fixed quantifier alternation depth is possible, which could lead to improved runtime bounds.
  • Rank-width vs. Clique-width: The paper mentions that all results could be straightforwardly reformulated for rank-width (and bi-rank-width for digraphs), which has the advantage of being computable by an FPT algorithm. However, the exposition focuses on clique-width for clarity.
  • Practical Implementation: The paper is theoretical, and the practical performance of these algorithms on real-world instances is not discussed. Further research could explore efficient implementations and empirical evaluations.

Summary updated

Abstract

In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, there still exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf. also Minimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches. The first part of the article deals with the Minimum Leaf Out-Branching problem and introduces a novel XP-time algorithm wrt. clique-width. We remark that this problem is known to be W[2]-hard, and that our algorithm does not resemble any of the previously published attempts solving special cases of it such as the Hamiltonian Path. The second part then looks at the Edge Disjoint Paths problem (both on graphs and digraphs) from a different perspective -- rather surprisingly showing that this problem has a definition in the MSO_1 logic of graphs. The linear-time FPT algorithm wrt. clique-width then follows as a direct consequence.
BibTeX
@inproceedings{ganian2011clique,
  author = {Robert Ganian and Petr Hlinený and Jan Obdrzálek},
  title = {{Clique-width: When Hard Does Not Mean Impossible}},
  booktitle = {STACS},
  year = {2011},
  doi = {10.4230/lipics.stacs.2011.404},
}

Loading related content...

Figure