Dynamic Programming for Graphs on Surfaces

Abstract : We provide a framework for the design of $2^{\mathcal{O}(k)}\cdot n$ step dynamic programming algorithms for surface-embedded graphs on $n$ vertices of branchwidth at most $k$. Our technique applies to graph problems for which dynamic programming uses tables encoding set partitions. For general graphs, the best known algorithms for such problems run in $2^{\mathcal{O}(k\cdot \log k)}\cdot n$ steps. That way, we considerably extend the class of problems that can be solved by algorithms whose running times have a {\em single exponential dependence} on branchwidth, and improve the running time of several existing algorithms. Our approach is based on a new type of branch decomposition called {\em surface cut decomposition}, which generalizes sphere cut decompositions for planar graphs, and where dynamic programming should be applied for each particular problem. The construction of such a decomposition uses a new graph-topological tool called {\em polyhedral decomposition}. The main result is that if dynamic programming is applied on surface cut decompositions, then the time dependence on branchwidth is {\sl single exponential}. This fact is proved by a detailed analysis of how non-crossing partitions are arranged on surfaces with boundary and uses diverse techniques from topological graph theory and analytic combinatorics.
Type de document :
Rapport
[Research Report] RR-7166, INRIA. 2009, pp.39
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00443582
Contributeur : Ignasi Sau Valls <>
Soumis le : mercredi 30 décembre 2009 - 17:21:40
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 17 juin 2010 - 22:13:12

Fichiers

RR-7166.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00443582, version 1

Citation

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. [Research Report] RR-7166, INRIA. 2009, pp.39. 〈inria-00443582〉

Partager

Métriques

Consultations de la notice

377

Téléchargements de fichiers

195