Miscellaneous
Fine-grained Complexity of Hard Geometric Problems: workshop @SoCG'18
Paweł Rzążewski and I are organizing a satellite workshop to SoCG 2018. The focus of the workshop is on algorithms and matching lower bounds for NP-hard geometric problems. If you want to contribute a talk to the workshop, just send Paweł and me an email. If you wish to attend (without giving a talk), don't hesitate to let us know. For more information, you can go directly to the workshop webpage.
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.