Dynamic programming for graphs on surfaces

✍ Scribed by Rué, Juanjo; Sau, Ignasi; Thilikos, Dimitrios M.

• Book ID: 125524861
• Publisher: Association for Computing Machinery
• Year: 2014
• Tongue: English
• Weight: 613 KB
• Volume: 10
• Category: Article
• ISSN: 1549-6325
• DOI: 10.1145/2556952

✦ Synopsis

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, 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 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.