DIMACS logo

Jan Kyncl

REU 2007

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 reachability

An input of the 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 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 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 the reachability on a fixed genus surface to the reachability in the plane. Previously, this was known only for the torus.

The result is described in the following paper:
Logspace reduction of directed reachability for bounded genus graphs to the planar case (with T. Vyskocil), ACM Transactions on Computation Theory 1 (2010), Issue 3, 1-11. doi:10.1145/1714450.1714451
preliminary version: ECCC Report TR09-050

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.

The result has been transformed into the following paper:
6-critical graphs on the Klein bottle (with K. Kawarabayashi, D. Kral and B. Lidicky), SIAM Journal on Discrete Mathematics 23 (2009), Issue 1, 372-383. doi:10.1137/070706835

Another group of researchers obtained the same result independently and approximately in the same time. We decided to write a joint extended abstract, which has been presented at the TGGT 2008 conference:
Six-Critical Graphs on the Klein Bottle (with N. Chenette, K. Kawarabayashi, D. Kral, B. Lidicky, L. Postle, N. Streib, R. Thomas and C. Yerger), Electronic Notes in Discrete Mathematics 31 (2008), 235-240.

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 a minimum vertex feedback set, that is, a set of vertices whose complement is an acyclic graph. We found a construction of a vertex feedback set of size at most (mn+4)/3, which exactly matches the lower bound when m,n>4.

In December 2008, we "accidentally" found a paper where the same result for the toroidal grids is proved: D. A. Pike, Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005), no. 3, 651-663. However, our construction is simpler.

The paper describing our results is almost finished:
Irreversible 2-conversion set is NP-complete (with B. Lidicky and T. Vyskocil), in preparation.
preliminary version: KAM-DIMATIA Series 2009-933


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.


Here you can find a final presentation of the first project.
If you are interested in Czech language, here you can find my pdf presentation. You can also find another material at Vitek's and Eva's page.

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.