Student: | Tomáš Toufar |
---|---|

Office: | 444 |

School: | Charles University in Prague |

E-mail: | tomast guess_what reu.dimacs.rutgers.edu |

Projects: | |

Complexity of Fair Deletion Problems | |

Simplifying Inclusion-Exclusion Formulas |

Many important algorithmic problems in graph theory can be stated as deletion problems – i.e. find a set such that graph satisfies certain property after deletion of such a set. Typically we look for a smallest such set but sometimes we want the set to be fair in some sense.

For example: find a set of edges after deletion of which a graph is acyclic while minimizing the maximal number of deleted edges incident with a vertex.

Our aim is to improve the metatheorem by Kolman et al.

- Fair edge deletion problems (Lishin Lin, Sartai Sahni)
- Fair edge deletion problems on tree-decomposable graphs an improper colorings (Petr Kolman, Bernard Lidický, Jean-Sébastien Sereni)

The principle of inclusion-exclusion is one of the classical topics of discrete mathematics. It allows one to compute the size of $F_1 \cup F_2 \cup \cdots \cup F_n$ given the size of all intersections of $F_i$'s by the formula $$ \bigg|\bigcup_{i=1}^n F_i\bigg| = \sum_{I: \emptyset \neq I \subseteq [n]} \bigg| \bigcap_{i \in I} F_i \bigg|.$$

Such formula has applications applications in mathematics and even in other fields. For instance, it can be used to compute accessible surface area of molecules in computational biology. It also gives best known algorithms for several NP-hard problems.

The inclusion-exclusion formula have exponential number of summands and this cannot be improved in general. However, given some restrictions of how can the sets $F_i$ intersect, there may be smaller formulas.

Our aim is to extend the results on finding exact inclusion-exclusion formulas with small coefficients and small number of terms.

- Simplifying inclusion-exclusion formulas (Xavier Goaoc, Jiří Matoušek, Pavel Paták, Zuzana Safernová, Martin Tancer)
- Inclusion-exclusion-Bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics (D.Q. Naiman, H.P. Wynn)

- Introduction, definition
- Presentation
- Reading articles

- Rewriting Kolman's metatheorem to use finite tree automata instead of $k$-terminal graphs
- Cultural day preparations

- Proven hardness of Kolman's metatheorem (not $FPT$ unless $FPT = W[1]$, cannot be computed in time $f(\tw(G)) n^{o(\sqrt[3]{\tw(G)})}$ unless Exponential time hypothesis fails)

- Proven aforementioned hardness result even for parameterization by pathwidth and feedback vertex set, the bound was improved to $f(\tw(G)) n^{o(\sqrt[2]{\tw(G)})}$

- We proved the $MSO_1$ version of metatheorem to be $FPT$ for parameterization by neighborhood diversity
- The original metatheorem ($MSO_2$ version) was proven to be $FPT$ for parameterization by vertex cover

http://www.mgvis.com/

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