Hello, I'm a first year PhD student at the Department of Applied Mathematics and the Institute for Theoretical Computer Science, at the Faculty of Mathematics and Physics of Charles University in Prague. I'm interested in combinatorics, graph theory and discrete geometry. In my master thesis I studied several problems concerning topological graphs.
I am working together with Tomas Vyskocil, Bernard Lidicky, Marek Sterzik, our graduate coordinator Jan Foniok and also with Daniel Kral, who visited us at DIMACS for a period of two weeks.
Our advisors are Michael Saks, Eric Allender and Van H. Vu.
We are working on the following problems:
Logspace and st-reachability
An input of the st-reachability problem is a directed graph G together with a pair of vertices s and t. The goal is to determine if s and t are connected by a directed path in G.
L (logspace) is the class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.) The class NL is a non-deterministic version of L.
It is known that st-reachability is a complete problem for NL, whereas the undirected version lies in L. We are trying to improve the complexity bounds on some related problems, for example the planar st-reachability, where the input is a planar graph, or some special versions of grid graph reachability, where the vertices of the graph are located on the vertices of the square grid and each edge connects only adjacent vertices of the grid.
Our results: We have found a logspace reduction from st-reachability on a fixed genus surface to the st-reachability in the plane. Previously, this was known only for the torus.
6-critical graphs in the Klein bottle
A 6-critical graph is an inclusion-minimal graph which is not 5-colorable. Our goal is to find a complete list of 6-critical graphs embeddable in the Klein bottle. By the result of Thomassen, this list has to be finite. Therefore, if we obtain this list, we will also have a polynomial algorithm for deciding 5-colorability of graphs embedded in the Klein Bottle. Such lists are already known for the torus and the projective plane (the only 6-critical graph for the projective plane is the complete graph on 6 vertices, for the torus the list consists of four graphs).
Our results: We have found a complete list of nine 6-critical graphs in the Klein bottle, together with their nineteen nonisomorphic embeddings.
Irreversible k-conversion set
Irreversible k-conversion set is a decision problem motivated by modelling the spread of infectious disease. The population is represented by a graph G where each person is represented by a vertex and the contacts between persons are represented by edges between the corresponding vertices. In the beginning, some set of vertices is infected. Then the disease spreads in steps. In each step, a healthy vertex becomes infected if it has at least k infected neighbors. An infected vertex is never cured. The input of a problem is a graph G and a positive integer p. The task is to determine whether there exists an initial subset of p infected vertices such that after finitely many steps every vertex of G becomes infected. This problem is NP-complete for k>=3, by a trivial reduction from the independent set problem. The open question was the complexity of the case k=2.
Our results: We proved that the 2-conversion set problem is NP-complete, even for graphs of maximum degree 4. For 3-regular graphs, this problem is equivalent to finding the minimum vertex feedback set (or the maximum induced forest), which is known to be polynomial.
We also considered the case k=3 for the toroidal grids of size m*n. In this case the minimum initial set of infected vertices causing the spread of the infection to all vertices is exactly the minimum vertex feedback set, that is, the set of vertices whose complement is an acyclic graph. We found a construction of the vertex feedback set of size at most (mn+4)/3, which exactly matches the lower bound when m,n>4.
Excercise:
A dining hall has 100 tables arranged in a 10*10 square grid. At each table, one student is sitting and he is eating his lunch. Unfortunately, some of the lunches were infected. The infection quickly spreads among the students by the following rule. A student becomes infected if at least two of his neighbors are infected (two students are neighbors if the two squares they are sitting in share an edge). After a while, each student became infected. Determine the minimum possible number of infected lunches at the beginning.
In 2004, I participated on the REU program as an undergraduate student. I was working with Eva Ondrackova, Tomas Valla Vit Jelinek and Zdenek Dvorak. The chief of our Prague group was Daniel Kral and our advisors were Alexander Soifer and Michael Saks.
The description of our REU projects was on Zdenek's page.