Student: | Pavel Dvořák |
---|---|

Office: | 444 |

School: | Charles University in Prague |

E-mail: | jajsem guess_what_is_here koblich.cz |

Project: | $L$-bounded cut |

**Week 1**- Choice of the problem
- Presentation about problem.
- Reading about FPT class [1].
- Reading about $W[P]$ class [2].

**Week 2****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.
- Talk about fourier tranform.
- Combinatorics bridge workshop.

**Week 6**- Writing a paper with the result.
- Fixing a minor error in the proof.
- Drawing fiqure of gadget.
- Talk about maritime security and robots, bridge workshop about number theory.

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

http://www.mgvis.com/

http://www.mgvis.com/AbelloVitaResearchOct08.html