HOME

TheInfoList



OR:

In
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
, Baker's technique is a method for designing
polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an in ...
s (PTASs) for problems on
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
s. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the ''
Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief An editor-in-c ...
'' in 1994. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. This technique has given PTASs for the following problems:
subgraph isomorphism In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomo ...
,
maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...
, minimum vertex cover,
minimum dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...
, minimum edge dominating set, maximum triangle matching, and many others. The bidimensionality theory of
Erik Demaine Erik D. Demaine (born February 28, 1981) is a professor of computer science at the Massachusetts Institute of Technology and a former child prodigy. Early life and education Demaine was born in Halifax, Nova Scotia, to artist sculptor Martin ...
, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot ''simplifying decompositions'' (,) generalizes and greatly expands the applicability of Baker's technique for a vast set of problems on
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
s and more generally graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the
1-planar graph In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural ...
s.


Example of technique

The example that we will use to demonstrate Baker's technique is the maximum weight independent set problem.


Algorithm

INDEPENDENT-SET(G, w, \epsilon) Choose an arbitrary vertex r k = 1/\epsilon find the breadth-first search levels for G rooted at r \pmod k: \ for \ell = 0, \ldots, k-1 find the components G^\ell_1, G^\ell_2, \ldots, of G after deleting V_\ell for i = 1,2, \ldots compute S_i^\ell, the maximum-weight independent set of G_i^\ell S^\ell = \cup_i S_i^\ell let S^ be the solution of maximum weight among \ return S^ Notice that the above algorithm is feasible because each S^\ell is the union of disjoint independent sets.


Dynamic programming

Dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...
is used when we compute the maximum-weight independent set for each G_i^\ell. This dynamic program works because each G_i^\ell is a k-outerplanar graph. Many NP-complete problems can be solved with dynamic programming on k-outerplanar graphs. Baker's technique can be interpreted as covering the given planar graphs with subgraphs of this type, finding the solution to each subgraph using dynamic programming, and gluing the solutions together.


References

* . * . * . * . * . * . * . * . *{{citation , last1 = Grigoriev , first1 = Alexander , last2 = Bodlaender , first2 = Hans L. , author2-link = Hans L. Bodlaender , doi = 10.1007/s00453-007-0010-x , issue = 1 , journal = Algorithmica , mr = 2344391 , pages = 1–11 , title = Algorithms for graphs embeddable with few crossings per edge , volume = 49 , year = 2007, hdl = 1874/17980 , s2cid = 8174422 , hdl-access = free . 1983 in computing Planar graphs Approximation algorithms