Dynamic programming for graphs on surfaces

DOI10.1007/978-3-642-14165-2_32MaRDI QIDQ3587392zbMATH OpenOpenAlexFDO

Authors Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.2486, https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083690/file/dprog.pdf

zbMATH Keywords

dynamic programminganalysis of algorithmsgraphs on surfacesnon-crossing partitionsparameterized algorithmsanalytic combinatoricsbranchwidthpolyhedral embeddingssymbolic method

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Abstract: We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2^{O(k log k)} n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", generalizing sphere cut decompositions of planar graphs introduced by Seymour and Thomas, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2^{O(k)} n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.

Recommendations

• Dynamic programming for graphs on surfaces
• Dynamic Programming for H-minor-free Graphs
• Cut and count and representative sets on branch decompositions
• STACS 2004
• Dynamic programming and planarity: improved tree-decomposition based algorithms

Cited in

(10)

• Dynamic programming for graphs on surfaces
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Parameterized domination in circle graphs
• On approximating the \(d\)-girth of a graph
• Graph minors and parameterized algorithm design
• Fast minor testing in planar graphs
• scientific article; zbMATH DE number 6783474 (Why is no real title available?)
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Confronting intractability via parameters
• Faster parameterized algorithms for minor containment

This page was built for publication: Dynamic programming for graphs on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587392)