Parameterized algorithm

The parameterized algorithms is a relatively new topic in theoretical computer science , is being studied in the detail which instances of NP-complete problems efficiently be solved. It is investigated on which factors ( parameters ) the running time of the algorithms essentially depends. For example, many graph problems can be solved quickly for graphs with a small tree width .

Formally, a problem can be parameterized (also: fixed parameter tractable or FPT ) if there is an algorithm that solves it with a running time of , where f is a calculable function, k is the parameter, p is any polynomial and n is the input length (e.g. . in graph problems the number of nodes and edges ). ${\ displaystyle f (k) \ cdot p (n)}$

Note that a problem with different parameters can be both FPT and non-FPT. For example, the clique problem is non-FPT when the parameter is the size of a maximum clique, but FPT when the parameter is the tree width or the maximum degree. It is also said that a problem can be parameterized in the corresponding parameter, e.g. B. "The clique problem can be parameterized in the tree width". A parameter in which an NP-complete problem can be parameterized is clear, a property that causes the exponential growth of the running times, since these problems can be solved quickly, except for instances in which this parameter is large.

In practice, f is often an awkward function like , but it is generally assumed that k is very small (because this is often the case with instances that occur in practice) and n can become large. In practice (where k is small), parameterized algorithms are also practicable for n = 50–100 , whereas z. B. ordinary brute-force algorithms with runtimes as already from about n = 20 are no longer practicable. ${\ displaystyle k ^ {k}}$ ${\ displaystyle O (2 ^ {n})}$

The area was established by Rod Downey and Michael Fellows in the 1990s.

FPT reduction

Similar to the polynomial time reduction , an FPT reduction is a function that can even be calculated in FPT time and maps an instance of a problem and the parameter to an instance of a problem and a parameter with the restriction . Then you write . ${\ displaystyle P_ {1}}$ ${\ displaystyle k_ {1}}$ ${\ displaystyle P_ {2}}$ ${\ displaystyle k_ {2}}$ ${\ displaystyle k_ {2} \ leq k_ {1}}$ ${\ displaystyle P_ {1} \ preceq _ {FPT} P_ {2}}$

This is a restriction compared to polynomial time reductions, because with these the size of the solution can change at will. So z. For example, with the polynomial time reduction of the independent set problem to the node coverage problem, the size of the minimum node coverage is the difference between the number of nodes and the size of the maximum independent set. So here is , so it's an i. A. unauthorized change in the size of the solution, which means that this is not an FPT reduction. Indeed, it turns out that the Independent Set Problem is W [1] -difficult , while the node coverage problem is FPT; That is, there is no FPT reduction from Independent Set to the node coverage problem if is. ${\ displaystyle k_ {2} = n-k_ {1} \ not \ leq k_ {1}}$ ${\ displaystyle P \ not = NP}$

Due to this restriction compared to polynomial time reductions, the FPT reduction provides a finer gradation of the complexity class NP and enables more precise statements about the complexity of NP-complete problems.

So, as from and it follows that is, it follows from and that is. Conversely, it follows that and W [t] -difficult, that W [t] -difficult, as follows from and the NP-severity of the NP-severity of . ${\ displaystyle L \ preceq _ {p} L ^ {\ prime}}$ ${\ displaystyle L ^ {\ prime} \ in P}$ ${\ displaystyle L \ in P}$ ${\ displaystyle L \ preceq _ {FPT} L ^ {\ prime}}$ ${\ displaystyle L ^ {\ prime} \ in FPT}$ ${\ displaystyle L \ in FPT}$ ${\ displaystyle L \ preceq _ {FPT} L ^ {\ prime}}$ ${\ displaystyle L}$ ${\ displaystyle L ^ {\ prime}}$ ${\ displaystyle L \ preceq _ {p} L ^ {\ prime}}$ ${\ displaystyle L}$ ${\ displaystyle L ^ {\ prime}}$

Limited computation trees

A frequently used method are calculation trees whose height and branching are restricted by functions in k . The branching can often even be restricted by constants. Such an algorithm can be used e.g. B. for the node coverage problem , where the parameter k is the size of a minimum node coverage.

One method here would be to choose any edge e that is not yet covered and to branch over the two nodes that are incident to e (one of the nodes is included in the node cover in each of the two branches of the calculation tree). The branch is therefore 2 and since one chooses a maximum of k nodes, the height of the calculation tree is limited by k . The choice of an edge that is not yet covered and the inclusion of a node in the node cover are possible in each case , which means that the overall runtime is off. ${\ displaystyle O (n)}$ ${\ displaystyle O (2 ^ {k} \ cdot n)}$

Problem core reduction

Fixed parameter tractable is a decidable problem if and only if there is a problem core reduction that can be calculated in polynomial time and that reduces an instance with parameter k to an instance whose size is limited by a function f (k) . The problem core can then be solved with an algorithm that has any finite running time h . This gives a total running time of h (f (k)) , which, together with the polynomial time for the reduction, still provides an FPT time limit.

This method can be used e.g. For example, to apply to the vertex coverage problem: If a vertex has a degree greater than k , it must be contained in a minimal vertex cover , because if a vertex v is not contained, all of its neighbors must be contained (since all edges that are incident to v are covered must), which would be more than k nodes, although k was defined as the size of a minimum node coverage.

After nodes have been selected in this way that must definitely be included in a minimum node coverage, a maximum of nodes can still be left ( k nodes for the node coverage and a maximum of k neighbors in each case ) from which a node coverage can be selected in steps. ${\ displaystyle k ^ {2} + k}$ ${\ displaystyle 2 ^ {k} \ cdot poly (n)}$

The size of the problem cores provides an even finer gradation of the complexity class FPT. For example, the node coverage problem is easier than the Min-Multicut problem on trees, although both are FPT, because the problem core of an instance of the node coverage problem (according to Nemhauser and Trotter) is at most 2k , whereas the best known problem core reduction for Min-Multicut on trees Delivers problem cores that are no larger than size . ${\ displaystyle k ^ {6}}$

Interleaving

The interleaving method is to carry out a problem core reduction before each recursion call. In general, this greatly reduces the runtime from to , where is the number of nodes in the calculation tree, the runtime of the expansion of a node in the calculation tree (the generation of the successors) and the runtime of the problem kernel reduction. ${\ displaystyle O (s (n, k) \ cdot t (n))}$ ${\ displaystyle O (s (n, k) + t (n) + r (n))}$ ${\ displaystyle s (n, k)}$ ${\ displaystyle t (n)}$ ${\ displaystyle r (n)}$

Interleaving is a powerful method to speed up programs for NP-difficult problems , especially in combination with memoization . This is because the instances that appear further down in the calculation tree have small parameters, which is why the problem cores are small and therefore there is a high probability that they will repeat themselves often, which means that the memoization can cut off many subtrees of the calculation tree.

Color coding

Another method is color coding , in which the n objects in the problem instance are “colored” with k colors. If a solution consists of k objects from the instance, it can often be found quickly if these k objects are colored differently. Then, they say that the solution colorful ( Engl. Colorful ) is. Since there are perfect hash functions , at most different colorings have to be tried until a solution is colorful, where c is a constant. ${\ displaystyle O (c ^ {k} \ cdot \ log (n))}$

With this method z. B. the search in a graph for a path of length k can be parameterized. If the nodes are colored differently on a path of length k , then the color classes on k! Species are arranged, all edges are removed that run between non-adjacent color classes, whereupon e.g. B. with the algorithm of Floyd and Warshall in can be checked whether there is still a path from a node of the first color class to a node of the last color class (if there is one, it has at least length k ). The running time of this algorithm is in , so it is an FPT algorithm. ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle O (c ^ {k} \ cdot k! \ cdot n ^ {3} \ cdot \ log (n))}$

Courcelles theorem

Courcelle's theorem states that every graph problem that can be described by an extended logic formula can be parameterized with the tree width as a parameter. An extended -logical formula is a logical formula with existence and universal quantifiers , which can quantify sets of nodes or edges, extended by a min and a max quantifier. ${\ displaystyle \ mathrm {MS} _ {2}}$ ${\ displaystyle \ mathrm {MS} _ {2}}$

Formulas from extended logic for the following problems on a graph G = (V, E) are e.g. B .: ${\ displaystyle \ mathrm {MS} _ {2}}$

Minimum node coverage: ${\ displaystyle \ min U \ subseteq V: \ forall e \ in E: \ exists v \ in U: \ operatorname {inc} (v, e)}$
Minimal dominant set of nodes : ${\ displaystyle \ min U \ subseteq V: \ forall v \ in V: (v \ in U \ vee \ exists v '\ in U: \ operatorname {adj} (v, v'))}$
Maximum clique : ${\ displaystyle \ max U \ subseteq V: \ forall v, v '\ in U: \ operatorname {adj} (v, v')}$

For classes of graphs that are characterized by the fact that a planar graph is forbidden as a minor , all these problems can be calculated in polynomial time because these graph classes each have a constant upper bound for the tree width. This concerns, for example, the class of triangulated graphs and the class of forests .

literature

Rod Downey, M. Fellows: Parameterized complexity . Springer, 1999, ISBN 0-387-94883-X .
Flum, J., Grohe, M .: Parameterized Complexity Theory . Springer, 2006, ISBN 978-3-540-29952-3 .
Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms . Oxford University Press, 2006, ISBN 0-19-856607-7 .
Marek Cygan, Fedir V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms . Springer International Publishing, 2016, ISBN 978-3-319-21274-6 , doi : 10.1007 / 978-3-319-21275-3 .