Composing dynamic programming tree-decomposition-based algorithms

Composing dynamic programming tree-decomposition-based algorithms

Blog Article

click here Given two integers $ell$ and $p$ as well as $ell$ graph classes $mathcal{H}_1,ldots,mathcal{H}_ell$, the problems $mathsf{GraphPart}(mathcal{H}_1, ldots, mathcal{H}_ell,p)$, reak $mathsf{VertPart}(mathcal{H}_1, ldots, mathcal{H}_ell)$, and $mathsf{EdgePart}(mathcal{H}_1, ldots, 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, ldots, 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, ldots, 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, ldots, mathcal{H}_ell,p)$, $mathsf{VertPart}(mathcal{H}_1, ldots, mathcal{H}_ell)$, and $mathsf{EdgePart}(mathcal{H}_1, ldots, mathcal{H}_ell)$.

We apply this approach to known problems.For well-studied problems, like VERTEX COVER and GRAPH read more $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.