Dynamic programming for graphs on surfaces

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

We provide a framework for the design and analysis of dynamic programming algorithms for surfaceembedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(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, 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 noncrossing 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 2O(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/improvemost previous results in this direction.

Original languageEnglish (US)
Article number8
JournalACM Transactions on Algorithms
Volume10
Issue number2
DOIs
StatePublished - Feb 2014

Keywords

  • Analysis of algorithms
  • Branchwidth
  • Dynamic programming
  • Graphs on surfaces
  • Noncrossing partitions
  • Parameterized algorithms
  • Polyhedral embeddings

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Dynamic programming for graphs on surfaces'. Together they form a unique fingerprint.

Cite this