×

zbMATH — the first resource for mathematics

Subexponential parameterized algorithms. (English) Zbl 1302.68340
Summary: We give a review of a series of techniques and results on the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch (or tree) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is the Bidimensionality Theory. Here we present not only the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of subexponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have \(2^{O(\sqrt{k})} \cdot n^{O(1)}\) time algorithms for a wide variety of parameterized problems on graphs, where \(n\) is the size of the graph and \(k\) is the parameter.

MSC:
68W40 Analysis of algorithms
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alber, J.; Bodlaender, H.L.; Fernau, H.; Kloks, T.; Niedermeier, R., Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 461-493, (2002) · Zbl 1016.68055
[2] Alber, J.; Bodlaender, H.L.; Fernau, H.; Niedermeier, R., Fixed parameter algorithms for planar dominating set and related problems, (), 97-110 · Zbl 0966.68224
[3] Alber, J.; Fan, H.; Fellows, M.R.; Fernau, H.; Niedermeier, R.; Rosamond, F.A.; Stege, U., Refined search tree technique for dominating set on planar graphs, (), 111-122 · Zbl 0999.68158
[4] Alber, J.; Fellows, M.R.; Niedermeier, R., Polynomial-time data reduction for dominating set, Journal of the ACM, 51, 363-384, (2004) · Zbl 1192.68337
[5] Alber, J.; Fernau, H.; Niedermeier, R., Parameterized complexity: exponential speed-up for planar graph problems, Journal of algorithms, 52, 26-56, (2004) · Zbl 1085.68102
[6] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete applied mathematics, 23, 11-24, (1989) · Zbl 0666.68067
[7] Björklund, A.; Husfeldt, T.; Kaski, P.; Koivisto, M., Fourier meets Möbious: fast subset convolution, (), 67-74 · Zbl 1232.68188
[8] Bodlaender, H., A tourist guide through treewidth, Acta cybernetica, 11, 1-23, (1993) · Zbl 0804.68101
[9] Bodlaender, H., On linear time minor tests with depth-first search, Journal of algorithms, 14, 1-23, (1993) · Zbl 0764.68107
[10] Bodlaender, H., A cubic kernel for feedback vertex set, (), 320-331 · Zbl 1186.68217
[11] Bodlaender, H., Treewidth: algorithmic techniques and results, (), 19-36 · Zbl 0941.05057
[12] Bodlaender, H.L.; Thilikos, D.M., Constructive linear time algorithms for branchwidth, (), 627-637 · Zbl 1401.05277
[13] Cai, L.; Juedes, D., On the existence of subexponential parameterized algorithms, Journal of computer and system sciences, 67, 789-807, (2003) · Zbl 1091.68121
[14] Chen, J.; Fernau, H.; Kanj, I.A.; Xia, G., Parametric duality and kernelization: lower bounds and upper bounds on kernel size, (), 269-280 · Zbl 1118.68506
[15] Deĭneko, V.G.; Klinz, B.; Woeginger, G.J., Exact algorithms for the Hamiltonian cycle problem in planar graphs, Operations research letters, 34, 3, 269-274, (2006) · Zbl 1089.05040
[16] E. Demaine, G.Z. Gutin, D. Marx, U. Stege, 07281 Abstracts Collection-Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, in: Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, n. 07281, 2007, p. 11 http://drops.dagstuhl.de/opus/volltexte/2007/1245
[17] Demaine, E.; Hajiaghayi, M., The bidimensionality theory and its algorithmic applications, The computer journal, 332-337, (2007)
[18] Demaine, E.D.; Fomin, F.V.; Hajiaghayi, M.; Thilikos, D.M., Bidimensional parameters and local treewidth, SIAM journal of discrete mathematics, 18, 501-511, (2004) · Zbl 1069.05070
[19] Demaine, E.D.; Fomin, F.V.; Hajiaghayi, M.; Thilikos, D.M., Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM transactions on algorithms, 1, 33-47, (2005) · Zbl 1321.05256
[20] Demaine, E.D.; Fomin, F.V.; Hajiaghayi, M.; Thilikos, D.M., Subexponential parameterized algorithms on graphs of bounded genus and \(H\)-minor-free graphs, Journal of the ACM, 52, 866-893, (2005) · Zbl 1326.05152
[21] E.D. Demaine, M. Hajiaghayi, Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica (in press) · Zbl 1174.05115
[22] Demaine, E.D.; Hajiaghayi, M., Bidimensionality: new connections between fpt algorithms and ptass, (), 590-601 · Zbl 1297.05056
[23] E.D. Demaine, M. Hajiaghayi, K. Kawarabayashi, Decomposition, approximation, and coloring of odd-minor-free graphs, manuscript · Zbl 1288.05053
[24] Demaine, E.D.; Hajiaghayi, M.; Thilikos, D.M., The bidimensional theory of bounded-genus graphs, SIAM journal of discrete mathematics, 20, 357-371, (2006), electronic · Zbl 1117.05100
[25] Demaine, E.D.; Hajiaghayi, M.T.; Nishimura, N.; Ragde, P.; Thilikos, D.M., Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of computer and system sciences, 69, 166-195, (2004) · Zbl 1073.68063
[26] Demaine, E.D.; Hajiaghayi, M.T.; Thilikos, D.M., Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors, Algorithmica, 41, 245-267, (2005) · Zbl 1065.68110
[27] Dorn, F., Dynamic programming and fast matrix multiplication, (), 280-291 · Zbl 1131.68484
[28] Dorn, F.; Fomin, F.V.; Thilikos, D.M., Fast subexponential algorithm for non-local problems on graphs of bounded genus, (), 172-183 · Zbl 1141.05338
[29] Dorn, F.; Fomin, F.V.; Thilikos, D.M., Catalan structures and dynamic programming in H-minor-free graphs, (), 631-640 · Zbl 1192.05155
[30] Dorn, F.; Penninkx, E.; Bodlaender, H.; Fomin, F.V., Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions, (), 95-106 · Zbl 1162.05354
[31] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer-Verlag New York · Zbl 0914.68076
[32] Feige, U.; Hajiaghayi, M.T.; Lee, J.R., Improved approximation algorithms for minimum-weight vertex separators [extended abstract], (), 563-572 · Zbl 1192.68893
[33] Fellows, M.R., Blow-ups, win/win’s, and crown rules: some new directions in fpt, (), 1-12 · Zbl 1255.68113
[34] Fernau, H.; Juedes, D.W., A geometric approach to parameterized algorithms for domination problems on planar graphs, (), 488-499 · Zbl 1096.68167
[35] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer-Verlag Berlin
[36] Fomin, F.V.; Thilikos, D.M., Fast parameterized algorithms for graphs on surfaces: linear kernel and exponential speed-up, (), 581-592 · Zbl 1099.68077
[37] Fomin, F.V.; Thilikos, D.M., Dominating sets in planar graphs: branch-width and exponential speed-up, SIAM journal on computing, 36, 281-309, (2006) · Zbl 1114.05072
[38] Fomin, F.V.; Thilikos, D.M., New upper bounds on the decomposability of planar graphs, Journal of graph theory, 51, 53-81, (2006) · Zbl 1085.05049
[39] Garey, M.R.; Johnson, D.S., Computers and intractability, A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York · Zbl 0411.68039
[40] A. Grigoriev, Large grid minors in planar graphs, manuscript, 2007
[41] Gu, Q.-P.; Tamaki, H., Optimal branch-decomposition of planar graphs in \(O(n^3)\) time, (), 373-384 · Zbl 1082.68591
[42] Gutin, G.; Kloks, T.; Lee, C.M.; Yeo, A., Kernels in planar digraphs, Journal of computer and system sciences, 71, 174-184, (2005) · Zbl 1170.68547
[43] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity, Journal of computer and system sciences, 63, 512-530, (2001) · Zbl 1006.68052
[44] Kanj, I.; Perković, L., Improved parameterized algorithms for planar dominating set, (), 399-410 · Zbl 1014.68218
[45] Levin, A.; Paulusma, D.; Woeginger, G.J., The complexity of graph contractions, (), 322-333 · Zbl 1255.68083
[46] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore, MD · Zbl 0979.05002
[47] Niedermeier, R., Invitation to fixed-parameter algorithms, (2006), Oxford University Press Oxford · Zbl 1095.68038
[48] Robertson, N.; Seymour, P.D., An outline of a disjoint paths algorithm, Paths, flows and VLSI design, algorithms and combinatorics, 9, 267-292, (1990) · Zbl 0759.05055
[49] Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, Journal of combinatorial theory. series B, 52, 153-190, (1991) · Zbl 0764.05069
[50] Robertson, N.; Seymour, P.D., Graph minors. XI. circuits on a surface, Journal of combinatorial theory. series B, 60, 72-106, (1994) · Zbl 0799.05016
[51] Robertson, N.; Seymour, P.D., Graph minors. XI. circuits on a surface, Journal of combinatorial theory. series B, 60, 72-106, (1994) · Zbl 0799.05016
[52] Robertson, N.; Seymour, P.D., Graph minors. XII. distance on a surface, Journal of combinatorial theory. series B, 64, 240-272, (1995) · Zbl 0840.05016
[53] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, Journal of combinatorial theory. series B, 63, 65-110, (1995) · Zbl 0823.05038
[54] Robertson, N.; Seymour, P.D., Graph minors. XVI. excluding a non-planar graph, Journal of combinatorial theory. series B, 89, 43-76, (2003) · Zbl 1023.05040
[55] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, Journal of combinatorial theory. series B, 62, 323-348, (1994) · Zbl 0807.05023
[56] Seymour, P.D.; Thomas, R., Call routing and the ratcatcher, Combinatorica, 14, 217-241, (1994) · Zbl 0799.05057
[57] D.M. Thilikos, H.L. Bodlaender, Constructive linear time algorithms for branchwidth, Tech. Rep. UU-CS-2000-38, Dept. of Computer Science, Utrecht University, 2000 · Zbl 1401.05277
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.