Dynamic Programming for Graphs on Surfaces

Juanjo Rué; Ignasi Sau Valls; Dimitrios M. Thilikos

inria-00443582, version 1

Dynamic Programming for Graphs on Surfaces

Juanjo Rué^a^, 1, Ignasi Sau Valls () ^2, 3, Dimitrios M. Thilikos^b^, 4

N° RR-7166 (2009)

a – Departament de Matemàtica Aplicada II - Universitat Politècnica de Catalunya
b – Department of Mathematics - National and Kapodistrian University of Athens
1: Departament de Matemàtica Aplicada II
http://www.ma2.upc.edu/
Universitat Politécnica de Catalunya Universitat Politècnica de Catalunya (UPC) Edifici Omega, Campus Nord Jordi Girona, 1-3 E-08034 Barcelona Spain Spain
2: MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271 France
3: Research Group on Graph Theory and Combinatorics [Barcelona]
http://www-mat.upc.es/grup_de_grafs/
Universitat Politécnica de Catalunya Universitat Politècnica de Catalunya Department of Applied Mathematics IV Campus Diagonal Nord, Building C3. C. Jordi Girona, 1-3. 08034 Barcelona Spain
4: Department of Mathematics (MPLA)
University of Athens National and Capodistrian University of Athens Panepistimiopolis 15784 Athens, Greece Greece

Bibliographic reference

Attached file list to this document:

PDF

RR-7166.pdf

(669.2 KB)

TEX

(29.1 KB)

(21 KB)

(11.7 KB)

(49.2 KB)

(1.7 KB)

(149.1 KB)

(61.7 KB)

(1.5 KB)

(17.3 KB)

(17.3 KB)

(18 KB)

(1.1 KB)

(19.5 KB)

(19.5 KB)

Logo-INRIA-couleur.ps

(35.1 KB)

Logo-INRIA-Futurs-couleur.ps

(25.7 KB)

Logo-INRIA-picto.ps

(24.4 KB)

Logo-INRIA-Sophia-couleur.ps

(28.5 KB)

Logo-INRIA-vertical.ps

(29.5 KB)

(39.6 KB)

(488.9 KB)

(12.2 KB)

(25.5 KB)

(26.5 KB)

(23.7 KB)

(17.8 KB)

(17.5 KB)

(18 KB)

(67.6 KB)

(27.5 KB)

(6.4 KB)

(1.2 MB)

inria-00443582, version 1
http://hal.inria.fr/inria-00443582
oai:hal.inria.fr:inria-00443582
From: Ignasi Sau Valls <>
Submitted on: Wednesday, 30 December 2009 17:21:40
Updated on: Thursday, 25 February 2010 14:16:51

See short view

Associated documents

PDF :

PS :

Export

Bibtex EndNote TEI RefWorks

%% inria-00443582, version 1
%% http://hal.inria.fr/inria-00443582
@techreport{rue:inria-00443582,
    hal_id = {inria-00443582},
    url = {http://hal.inria.fr/inria-00443582},
    title = {{Dynamic Programming for Graphs on Surfaces}},
    author = {Ru{\'e}, Juanjo and Sau Valls, Ignasi and Thilikos, Dimitrios M.},
    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.}},
    language = {English},
    affiliation = {Departament de Matem{\`a}tica Aplicada II , MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Research Group on Graph Theory and Combinatorics [Barcelona] , Department of Mathematics - MPLA},
    pages = {39},
    type = {Research Report},
    institution = {INRIA},
    number = {RR-7166},
    year = {2009},
    month = Dec,
    pdf = {http://hal.inria.fr/inria-00443582/PDF/RR-7166.pdf},
}

%F inria-00443582, version 1
%0 Report
%U http://hal.inria.fr/inria-00443582
%2 MATH:MATH_CO
%T Dynamic Programming for Graphs on Surfaces
%A Rué, Juanjo
%A Sau Valls, Ignasi
%A Thilikos, Dimitrios M.
%+ Departament de Matemàtica Aplicada II , MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Research Group on Graph Theory and Combinatorics [Barcelona] , Department of Mathematics - MPLA
%X 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.
%2 F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics, G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms
%G English
%2 Research Report
%P 39
%8 2009-12-30
%Z RR-7166