On 10.03.2016 at 12:20 in S6, there is the following noon lecture:
Parameterized complexity of length-bounded cuts (Jirka Matoušek Prize talk)
The minimal length-bounded L-cut problem is to compute for a given integer L, a graph G, a source s and a sink t a set of edges F, such that if we remove all edges F from the graph the length of the shortest path between s and t in the resulting graph has at least L edges.
We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters.
It is possible to derive an FPT algorithm for the minimal length-bounded L-cut when parametrized by the tree-depth only.
On the other hand the minimal length-bounded L-cut problem is W-hard when parametrized by path-width.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019