### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) |

Editors | G. Gutin, S. Szeider |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 41-53 |

Number of pages | 13 |

ISBN (Print) | 978-3-319-03897-1 |

DOIs | |

Publication status | Published - Sep 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 8246 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Fingerprint

### Keywords

- EWI-23839
- tree decomposition
- Graph algorithms
- IR-88274
- Treewidth
- METIS-300088
- Dynamic Programming

### Cite this

*Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)*(pp. 41-53). (Lecture Notes in Computer Science; Vol. 8246). Berlin: Springer. https://doi.org/10.1007/978-3-319-03898-8_5

}

*Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013).*Lecture Notes in Computer Science, vol. 8246, Springer, Berlin, pp. 41-53. https://doi.org/10.1007/978-3-319-03898-8_5

**The fine details of fast dynamic programming over tree decompositions.** / Bodlaender, Hans L.; Bonsma, P.S.; Lokshtanov, Daniel.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The fine details of fast dynamic programming over tree decompositions

AU - Bodlaender, Hans L.

AU - Bonsma, P.S.

AU - Lokshtanov, Daniel

PY - 2013/9

Y1 - 2013/9

N2 - We study implementation details for dynamic programming over tree decompositions. Firstly, a fact that is overlooked in many papers and books on this subject is that it is not clear how to test adjacency between two vertices in time bounded by a function of $k$, where $k$ is the width of the given tree decomposition. This is necessary to obtain linear time dynamic programming algorithms. We address this by giving a simple $O(kn)$ time and space preprocessing procedure that enables adjacency testing in time $O(k)$, where $n$ is the number of vertices of the graph. Secondly, we show that a large class of NP-hard problems can be solved in time $O(q^{k+1} n)$, where $q^{k+1}$ is the natural size of the dynamic programming tables. The key improvement is that we avoid a polynomial factor in $k$. This holds for all problems that can be formulated as a Min Weight Homomorphism problem: given a (di)graph $G$ on $n$ vertices and a (di)graph $H$ on $q$ vertices, with integer vertex and edge weights, is there a homomorphism from $G$ to $H$ with total (vertex and edge image) weight at most $M$? This result implies e.g.\ $O(2^k n)$ algorithms for Max Independent Set and Max Cut, and a $O(q^{k+1} n)$ algorithm for $q$-Colorability. The table building techniques we develop are also useful for many other problems.

AB - We study implementation details for dynamic programming over tree decompositions. Firstly, a fact that is overlooked in many papers and books on this subject is that it is not clear how to test adjacency between two vertices in time bounded by a function of $k$, where $k$ is the width of the given tree decomposition. This is necessary to obtain linear time dynamic programming algorithms. We address this by giving a simple $O(kn)$ time and space preprocessing procedure that enables adjacency testing in time $O(k)$, where $n$ is the number of vertices of the graph. Secondly, we show that a large class of NP-hard problems can be solved in time $O(q^{k+1} n)$, where $q^{k+1}$ is the natural size of the dynamic programming tables. The key improvement is that we avoid a polynomial factor in $k$. This holds for all problems that can be formulated as a Min Weight Homomorphism problem: given a (di)graph $G$ on $n$ vertices and a (di)graph $H$ on $q$ vertices, with integer vertex and edge weights, is there a homomorphism from $G$ to $H$ with total (vertex and edge image) weight at most $M$? This result implies e.g.\ $O(2^k n)$ algorithms for Max Independent Set and Max Cut, and a $O(q^{k+1} n)$ algorithm for $q$-Colorability. The table building techniques we develop are also useful for many other problems.

KW - EWI-23839

KW - tree decomposition

KW - Graph algorithms

KW - IR-88274

KW - Treewidth

KW - METIS-300088

KW - Dynamic Programming

U2 - 10.1007/978-3-319-03898-8_5

DO - 10.1007/978-3-319-03898-8_5

M3 - Conference contribution

SN - 978-3-319-03897-1

T3 - Lecture Notes in Computer Science

SP - 41

EP - 53

BT - Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)

A2 - Gutin, G.

A2 - Szeider, S.

PB - Springer

CY - Berlin

ER -