Tools

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 in his track. It is quite an understatement since he solved (almost) all the instances! He has been developing what he calls positive-instance driven (PID) dynamic programming. This happens to be a very versatile approach to solve Treewidth, Minimum Fill-In, but also Coloring problems. He will present his work at ESA in Vienna in September 2017.

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.