TY - GEN

T1 - Dynamic programming for graphs on surfaces

AU - Rué, Juanjo

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2010

Y1 - 2010

N2 - 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 20(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, capturing how partial solutions can be arranged on a surface. Then we use singularity analysis over expressions obtained by the symbolic method to prove 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 20(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 all previous results in this direction.

AB - 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 20(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, capturing how partial solutions can be arranged on a surface. Then we use singularity analysis over expressions obtained by the symbolic method to prove 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 20(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 all previous results in this direction.

KW - analysis of algorithms

KW - analytic combinatorics

KW - branchwidth

KW - dynamic programming

KW - graphs on surfaces

KW - non-crossing partitions

KW - parameterized algorithms

KW - polyhedral embeddings

KW - symbolic method

UR - http://www.scopus.com/inward/record.url?scp=77955314466&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955314466&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14165-2_32

DO - 10.1007/978-3-642-14165-2_32

M3 - Conference contribution

AN - SCOPUS:77955314466

SN - 3642141641

SN - 9783642141645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 372

EP - 383

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -