Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar: Proposed Topics

A Crossing Lemma for Multigraphs

Janos Pach and Geza Toth.
A Crossing Lemma for Multigraphs.
34th International Symposium on Computational Geometry (SoCG 2018).

The famous Crossing Lemma by Ajtai et al. gives a lower bound on the number of crossings that a given graph must have when drawn in the plane, in terms of the number of vertices and edges. This paper studies generalizations of the statement that also apply to multigraphs. In particular, for the special class of so called branching drawings, the authors get rid of the dependency on the maximum multiplicity of an edge, as seen in an earlier paper by Szekely.

In your talk you should give a broad overview over all known results related to the Crossing Lemma. After that you would try to go into some detail and explain how the proof in the paper works, and how it compares to the classic proofs.

Contact: Manuel Wettstein, manuelwe@inf.ethz.ch, CAB G 38.

Classic Nintendo Games are (Computationally) Hard

Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.
Classic Nintendo Games are (Computationally) Hard.
Theoretical Computer Science 586 (2015), 135-160.

The paper analyzes for several Nintendo games the decision problem of reachability: given a stage, is it possible to reach the goal point t from the start point s? This Problem is shown to be NP-hard for Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. It is also proved that for some versions of Donkey Kong and Legend of Zelda, the problem is PSPACE-complete.

In your talk you would present the general framework of the reductions and then apply this framework to some of the games.

Contact: Patrick Schnider, schnpatr@inf.ethz.ch, CAB G 36.2, Tel. 044-632 6417.

EPTAS for Max Clique on Disks and Unit Balls

Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, and Stephan Thomasse.
EPTAS for Max Clique on Disks and Unit Balls.
2018.

The problem of finding a maximum clique on a graph is NP-hard. It is a long-standing problem to know what happens when we restrict the graphs considered to be disk graphs. It is known since the 90s that the problem of maximum clique can be solved in polynomial time if all the disks have the same radius. This paper gives an efficient polynomial-time approximation scheme (EPTAS) for maximum clique on disk graphs with arbitrary radii. Their algorithm also works when considering unit ball graphs. On the contrary, they show that when considering ball graphs and unit 4-dimensional disk graphs, the problem becomes NP-hard and does not admit a PTAS.

In your talk you should present the differences on finding a maximum clique on d-dimensional disks graphs, depending on the dimension d (between 2 and 4), and depending on whether the disks are unit. You should explain what properties make the problem easy or hard.

Contact: Nicolas Grelier, nicolas.grelier@inf.ethz.ch, CAB G 19.2.