DIMACS
DIMACS REU 2014

General Information

me
Student: Pavel Dvořák
Office: 444
School: Charles University in Prague
E-mail: jajsem guess_what_is_here koblich.cz
Project: $L$-bounded cut

Project Description

Let $(V, E, s, t, c)$ be a network. $L$-bounded cut $F$ is subset of $E$ such that network $(V, E \setminus F, s, t, c)$ does not contain any $s$-$t$ path of length $L$ or smaller. The problem is NP-hard for $4 \leq L \leq n^{1 - \epsilon}$. We know FPT algoritm for parameters $L$ and $tw$. We also know the problem parametrized only by $L$ is Para-NP-complete. Our goal is to prove hardness of the problem parametrized only by tree-width.

Current activities

References

[1] Jörg Flum, Martin Gröhe, Parametrized Complexity Theory, ISBN 3-540-29952-1, Chapter 1.
[2] Jörg Flum, Martin Gröhe, Parametrized Complexity Theory, ISBN 3-540-29952-1, Chapter 3.
[3] Jörg Flum, Martin Gröhe, Parametrized Complexity Theory, ISBN 3-540-29952-1, Chapter 7.
[4] Marco Cesati, Compendium of Parameterized Problems.
[5] Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger, Capacitated domination and covering: A parameterized perspective, in IWPEC'08, vol. 5018 of LNCS, Springer, 2008, pp. 78-90.

Coworkers

Presentations


Additional Information

My Mentor
  • Professor James Abello
        http://www.mgvis.com/
        http://www.mgvis.com/AbelloVitaResearchOct08.html