## Abstract

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.

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

Title of host publication | Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Revised Selected Papers |

Pages | 41-53 |

Number of pages | 13 |

DOIs | |

Publication status | Published - 2013 |

Externally published | Yes |

Event | 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) - Sophia Antipolis, France Duration: 4 Sep 2013 → 6 Sep 2013 Conference number: 8 |

### Publication series

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

Volume | 8246 |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) |
---|---|

Abbreviated title | IPEC 2013 |

Country | France |

City | Sophia Antipolis |

Period | 4/09/13 → 6/09/13 |

Other | 8th International Symposium on Parameterized and Exact Computation |