moteur de recherche

Séminaire Algo - Nils Morawietz
Séminaire Algo - Nils Morawietz
13-Oct-2020 14:00
Age: 246 days

 (Philipps-Universität Marburg, Germany)

New parameterized complexity results for Colored (s,t)-cut


In the Colored (s,t)-cut problem, the input is a graph G=(V,E) together with an edge-coloring l mapping E to C, two vertices s and t, and a number k. The question is whether there is a subset S of C containing at most k colors, such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-cut.
First, we consider parameters related to the coloring l. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C|. Second, we consider parameterizations by the vertex cover number vc and the budget k. We present an algorithm solving Colored (s,t)-cut in 2^{vc + k} * n^{O(1)} time and a polynomial kernel of size O((vc*k)²)..

<- Back to: Accueil