### General Information

Student: Pavel Dvořák 444 Charles University in Prague jajsem guess_what_is_here koblich.cz $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

• Week 1
• Choice of the problem
• Reading about $W[P]$ class [2].
• Week 2
• Reading about $W$-hierarchy [3].
• Try to find hard problem for reduction
• Reading the list of hard problems in $W$-hierarchy [4].
• Capacitated vertex cover is $W[1]$-hard [5]. in tree-width
• Week 3
• Trying to make reduction to capacitated vertex cover.
• Excellent talk from Patrick Devlin about generating functions.
• Bridge workshop about graph theory
• Discover that capacitated vertex cover is actually $W[1]$-hard in path-width.
• Week 4
• Capacitated vertex cover might not be a good candidate for reduction. I could not realised some gadget, where the size of cut can be controlled.
• Trying to make reduction from multicolor clique.
• Bridge workshop about ramsey theory.
• Making presentation for cultural day.
• Week 5
• Finish proof about $W[1]$-hardness.
• Reduction from multicolor clique.
• Combinatorics bridge workshop.
• Week 6
• Writing a paper with the result.
• Fixing a minor error in the proof.
• Talk about maritime security and robots, bridge workshop about number theory.

### 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.