Vendredi 14 juin 2013, 14h, en salle 201, Binh Minh Bui Xuan, chargé de recherche au LIP6 (joint work with J.-F. Raymond and P. Trebuchet)
A major trend in parameterized algorithms aims at solving NP-hard graph problems in two steps: (1) recursively divide the input graph into chunks not increasing the value of a certain "width" parameter; (2) solve the NP-hard problem at hand along the chunk divisions. The two stage divide-and-conquer paradigm is commonly addressed as (1) finding good heuristics/approximation for the width parameter; (2) dynamic programming solving the NP-hard problem at hand .
From this perspective treewidth has made its mark in research history as a celebrated notion (that also set the stone for numerous other fruitful research fields). It is still the only parameter boasting very advance libraries for both stage (1) and (2) algorithms. This aspect alone has resulted in thousands of papers at the same time theoretical and applicative with treewidth being the main keyword. Unfortunately, the value of treewidth is high on dense graphs, thus fundamentally ruining the whole algorithmic approach on these graph instances*. For decades, a lot of research effort have been put in pointing out elements that would help rectifying the situation: cliquewidth from graph rewriting, rankwidth from graph algebra, booleanwidth from graph algorithms.
We present experimental results on par with treewidth on regular graphs, while also handle dense graphs in polynomial time. This is achieved by focusing on rankwidth, an algebraic version of treewidth very useful for having deep matroid properties [S. Oum and P. Seymour, Journal of Combinatorial Theory series B, 2006], and booleanwidth, an algorithmic version of rankwidth particularly well suited for dynamic programming [B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoretical Computer Science, 2011].
----------
*The phenomenon culminates with the compete graph having treewidth linear in the size of the graph itself. Treewidth based algorithms suffer from this bottleneck and have no other alternative but to perform poorly on these instances. For instance, it -will- take an exponential runtime for a generic treewidth based algorithm to solve Independent Set on a complete graph, unless Independent Set can itself be solved in subexponential time on -all- graphs. Since it is trivial to solve Independent Set on a complete graph, it has been a major challenge of the past decades to improve treewidth by proposing a better valued parameter.
