Dynamic programming for graphs on surfaces

DOI10.1007/978-3-642-14165-2_32zbMATH Open1288.05286arXiv1104.2486OpenAlexW2569141772MaRDI QIDQ3587392FDOQ3587392

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

Publication date: 7 September 2010

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

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.

Full work available at URL: https://arxiv.org/abs/1104.2486

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

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)

Cited In (10)

• 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
• Title not available (Why is that?)
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Confronting intractability via parameters
• Faster parameterized algorithms for minor containment
• Dynamic programming for graphs on surfaces

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)