## Samenvatting

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2^{O(tw)}|^{V|O(1)} for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than twO(^{tw)}|^{V|O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time ^{ctw}|^{V|O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic ^{ctw}|^{V|O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

Originele taal-2 | Engels |
---|---|

Pagina's (van-tot) | 86-111 |

Aantal pagina's | 26 |

Tijdschrift | Information and Computation |

Volume | 243 |

DOI's | |

Status | Gepubliceerd - 1 aug. 2015 |

Evenement | 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) - University of Latvijas, Riga, Letland Duur: 8 jul. 2013 → 12 jul. 2013 Congresnummer: 40 http://www.icalp2013.lu.lv/ |