Composing dynamic programming tree-decomposition-based algorithms

Abstract

Given two integers $\ell$ and $p$ as well as $\ell$ graph classes ${\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell }$, the problems $\mathsf{GraphPart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell },p)$, \break $\mathsf{VertPart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell })$, and $\mathsf{EdgePart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell })$ ask, given graph $G$ as input, whether $V(G)$, $V(G)$, $E(G)$ respectively can be partitioned into $\ell$ sets $S_1,\dots ,S_{\ell }$ such that, for each $i$ between $1$ and $\ell$, $G[S_i]\in {\mathcal{H}}_i$, $G[S_i]\in {\mathcal{H}}_i$, $(V(G),S_i)\in {\mathcal{H}}_i$ respectively. Moreover in $\mathsf{GraphPart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell },p)$, we request that the number of edges with endpoints in different sets of the partition is bounded by $p$. We show that if there exist dynamic programming tree-decomposition-based algorithms for recognizing the graph classes ${\mathcal{H}}_i$, for each $i$, then we can constructively create a dynamic programming tree-decomposition-based algorithms for $\mathsf{GraphPart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell },p)$, $\mathsf{VertPart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell })$, and $\mathsf{EdgePart}({\mathcal{H}}_1,\dots ,{\mathcal{H}}_{\ell })$. We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH $q$-COLORING, we obtain running times that are comparable to those of the best known problem-specific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth.

References in corpus (2)

• Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
• Treewidth of display graphs: bounds, brambles and applications