TY - GEN

T1 - Fast sub-exponential algorithms and compactness in planar graphs

AU - Thilikos, Dimitrios M.

PY - 2011

Y1 - 2011

N2 - We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r,q)-compact when all the faces and vertices of its YES-instances are "r-radially dominated" by some vertex set whose size is at most q times the parameter. We prove that if a parameterized problem can be solved in steps and is (r,q)-compact, then it can be solved by a cr.2.122.√q.kno(1) step algorithm (where k is the parameter). Our framework is general enough to unify the analysis of almost all known sub-exponential parameterized algorithms on planar graphs and improves or matches their running times. Our results are based on an improved combinatorial bound on the branchwidth of planar graphs that bypasses the grid-minor exclusion theorem. That way, our approach encompasses new problems where bidimensionality theory do not directly provide sub-exponential parameterized algorithms.

AB - We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r,q)-compact when all the faces and vertices of its YES-instances are "r-radially dominated" by some vertex set whose size is at most q times the parameter. We prove that if a parameterized problem can be solved in steps and is (r,q)-compact, then it can be solved by a cr.2.122.√q.kno(1) step algorithm (where k is the parameter). Our framework is general enough to unify the analysis of almost all known sub-exponential parameterized algorithms on planar graphs and improves or matches their running times. Our results are based on an improved combinatorial bound on the branchwidth of planar graphs that bypasses the grid-minor exclusion theorem. That way, our approach encompasses new problems where bidimensionality theory do not directly provide sub-exponential parameterized algorithms.

KW - Branchwidth

KW - Parameterized Algorithms

KW - Planar Graphs

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

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

U2 - 10.1007/978-3-642-23719-5_31

DO - 10.1007/978-3-642-23719-5_31

M3 - Conference contribution

AN - SCOPUS:80052785445

SN - 9783642237188

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

SP - 358

EP - 369

BT - Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings

T2 - 19th Annual European Symposium on Algorithms, ESA 2011

Y2 - 5 September 2011 through 9 September 2011

ER -