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(
,
,
)
Choose an arbitrary vertex
find the breadth-first search levels for
rooted at
:
for
find the components
of
after deleting
for
compute
, the maximum-weight independent set of
let
be the solution of maximum weight among
return
Notice that the above algorithm is feasible because each
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
. This dynamic program works because each
is a
-outerplanar graph. Many NP-complete problems can be solved with dynamic programming on
-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