Clique-width: When Hard Does Not Mean Impossible

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 (or, 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 highly non-standard new approaches. In the first part – for the Minimum Leaf Out-Branching problem, which has remained open till now despite attempting various traditional approaches based on dynamic programming – we design an inspiring novel XP-time algorithm wrt. clique-width. We remark that this problem is known to be W[2]-hard, and that our algorithm is very different from 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 an unexpected perspective – rather surprisingly showing that this problem has an involved definition in the MSO1 logic of graphs, i.e. a logic not capable of quantification over edges. A linear-time FPT algorithm for Edge Disjoint Paths wrt. clique-width is then a straightforward consequence