An Overview of Techniques for Designing Parameterized Algorithms <s> Example: k-dominating set <s> Suppose we expect there to bep(ab) phone calls between locationsa andb, all choices ofa, b from some setL of locations. We wish to design a network to optimally handle these calls. More precisely, a “routing tree” is a treeT with set of leavesL, in which every other vertex has valency 3. It has “congestion” 0 form the edges of a planar graphG, there is an efficient, strongly polynomial algorithm. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> Example: k-dominating set <s> We present an algorithm that constructively produces a solution to the k-DOMINATING SET problem for planar graphs in time O(c k n), where c = 4 634 . To obtain this result, we show that the treewidth of a planar graph with domination number y(G) is O(γ(G)), and that such a tree decomposition can be found in O(γ(G)n) time. The same technique can be used to show that the k-FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c k 1n ) time, where c 1 = 3 3634 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k-DOMINATING SET, e.g., k-INDEPENDENT DOMINATING SET and k-WEIGHTED DOMINATING SET. <s> BIB002 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> Example: k-dominating set <s> We demonstrate a new connection between fixed-parameter tractability and approximation algorithms for combinatorial optimization problems on planar graphs and their generalizations. Specifically, we extend the theory of so-called "bidimensional" problems to show that essentially all such problems have both subexponential fixed-parameter algorithms and PTASs. Bidimensional problems include e.g. feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal problems, dominating set, edge dominating set, r-dominating set, diameter, connected dominating set, connected edge dominating set, and connected r-dominating set. We obtain PTASs for all of these problems in planar graphs and certain generalizations; of particular interest are our results for the two well-known problems of connected dominating set and general feedback vertex set for planar graphs and their generalizations, for which PTASs were not known to exist. Our techniques generalize and in some sense unify the two main previous approaches for designing PTASs in planar graphs, namely, the Lipton-Tarjan separator approach [FOCS'77] and the Baker layerwise decomposition approach [FOCS'83]. In particular, we replace the notion of separators with a more powerful tool from the bidimensionality theory, enabling the first approach to apply to a much broader class of minimization problems than previously possible; and through the use of a structural backbone and thickening of layers we demonstrate how the second approach can be applied to problems with a "nonlocal" structure. <s> BIB003
Let us briefly explain this technique in the case of finding k-dominating sets in planar graphs, where a very lowtreewidth bound on Yes-instances gives very fast FPT algorithms. In BIB002 , it is shown that a planar graph that has a k-dominating set has treewidth at most c p k for an appropriate constant c. Thus, we have a win/win relationship, since we can check in polynomial time if a planar graph has treewidth at most c 0 p k BIB001 , for some slightly larger constant c 0 , and if so find a tree-decomposition of this width. If the treewidth is higher we can safely reject the instance, and otherwise we can run a dynamic programming algorithm on its treedecomposition, parameterized by c 0 p k, to find in FPT time the optimal solution. In total this gives a O*(c 00 p k) algorithm for deciding if a planar graph has a dominating set of size k. A series of papers have lowered the constant c 00 of this algorithm, by several techniques, like moving to branchwidth instead of treewidth, by improving the constant c and by improving the FPT runtime of the dynamic programming stage. Yet another series of papers have generalized these 'subexponential in k' FPT algorithms from dominating set to all so-called bidimensional parameters and also from planar graphs to all graphs not having a fixed graph H as minor BIB003 .