Miscellaneous

PACE 2018: Steiner Tree


The PACE 2018 challenge has started! The goal of PACE (the Parameterized Algorithms and Computational Experiments Challenge) is to investigate the practical applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. This year there is only one problem, Steiner Tree, and three tracks: two for exact algorithms and one for heuristics. Florian Sikora and I are organising; don't hesitate to send us questions and comments. You may already register your team and find out all the details of the challenge. For that, visit the PACE 2018 page.

Erdős-Szekeres theorem proven in 6 Nimmt! rules


The Erdős-Szekeres theorem states that in any sequence of n² real numbers there is a monotone subsequence of length n. Actually, it says something slightly stronger: in any sequence of (s-1)(r-1)+1 real numbers there is either an increasing subsequence of length s or a decreasing subsequence of length r. Erdős and Szekeres proved this result in 1935, Abraham Seidenberg wrote a 8-line proof in 1958, and J. Michael Steel surveyed some of the several existing proofs in 1995.

One simple proof is contained in the rule of Wolfgang Kramer's card game 6 Nimmt! (Take 5!). The important thing in the rules is how a card that you play is placed on the table: the card goes on top of the stack where the current top card is the largest among the stacks with a smaller card on top. If all the stacks have on top a higher card, then a new stack is created (well, this is not exactly true in the game). Now the proof. Take your n²-card sequence and play it out according to those rules. Each time you do not play in the first stack, draw on the table a pointer going from the card you just played to the current top card in the previous stack.

In the end, either you have a stack of height at least n, which constitutes an increasing subsequence of length n, or you have more than n stacks, and following the pointers from the last stack and reversing gives you a decreasing subsequence of length n.

Sources to solve Minimum Fill-In a.k.a Chordal Completion (in python)


With R. B. Sandeep and Florian Sikora, we participated in the second edition of the PACE challenge. The goal was to solve the most of 100 instances of Minimum Fill-In, being given 30 minutes per instance, using parameterized algorithms and no (M)ILP nor SAT solvers. Minimum Fill-In, also called Chordal Completion, consists of finding a smallest set of edges to add to a graph to make it chordal; i.e., the graph does not contain an induced cycle of length at least four. This problem is surprisingly tricky. For instance, the exact optimal value is not known on graphs as simple as grids.

Around 2000, Vincent Bouchitté and Ioan Todinca developed in a series of papers a nice theory of so-called potential maximal cliques, in order to solve efficiently Treewidth and Minimum Fill-In on some classes of graphs. This theory would be later used by Fedor Fomin and Yngve Villanger to design a parameterized subexponential time algorithm running in 2O(√ k  log k). Sandeep together with Yixin Cao showed that this algorithm is essentially optimal under the Exponential Time Hypothesis.

We implemented the approach of Bouchitté and Todinca based on listing the potential maximal cliques and some home-made heuristics to compute upper bounds on the size of the solution to prune the search. Obtaining good lower bounds would speed up our code but appear really challenging. Here is a general presentation of the algorithm and the python sources can be found there. We finished third; more importantly, we learnt things and had fun in the process.

Hisao Tamaki has participated in both editions of PACE and convincingly won with his team. He has been developing what he calls positive-instance driven (PID) dynamic programming. This happens to be a very versatile approach to solve efficiently Treewidth, Minimum Fill-In, and thereby most of the problems with moderate treewidth. He presented his ESA best paper at ALGO 2017 in Vienna.

A simple and modular generator of TikZ code to draw random graphs (in python)


One admittedly fair criticism that I often hear about TikZ for drawing graphs is that you have to set the coordinates of your vertices manually, and go back and forth between the tex file and the pdf when you adjust their positions. It is time-consuming if you compare that to just clicking where you want to create a new vertex in any drawing software. And some of those softwares offer you the possibility of exporting in tex/TikZ what you've drawn.

Although, more often than not when we draw graphs, we are not drawing a specific graph but rather any kind of reasonable-looking instance where we will illustrate some structural properties, the run of an algorithm, etc. In that case, clicking is also a waste of time.

In that very situation, you can use this python file which will produce for you the TikZ code of random graphs. Scroll down to the end of the file and customize your options. The function tikzGraphAndCompile will produce the tex file graph.tex, and try to compile it with pdflatex and open the output with okular. You may want to change that to what you're actually using. You can also use the function tikzGraph which only outputs the tex code.

I recommend to set the labels on, make your specific edits, and eventually remove the labels in the tex file either manually or with a regexp (something like {$*$}; becomes {};). Obviously, the labels will help you to know what is where.

An example of a generated vertex-colored planar graph with 2000 vertices; here is the tex code.



For a practical use, you might want to put far less vertices.