General Information

Student: Tomáš Toufar
Office: 444
School: Charles University in Prague
E-mail: tomast guess_what reu.dimacs.rutgers.edu
  Complexity of Fair Deletion Problems
  Simplifying Inclusion-Exclusion Formulas

Complexity of Fair Deletion Problems

Project Description

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.

Previous work

Simplifying Inclusion-Exclusion Formulas

Project description

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.

Previous work

Current activities

First week

Second week

Third week

Fourth week

Fifth week


Additional Information

My Mentor
  • Professor James Abello