Speaker: Benjamin Bergougnoux
Title: A new notion of Representative Sets for Graph Coloring
Abstract: Many efficient algorithms have been designed for Graph Coloring parameterized by width parameters such as tree-width, clique-width, rank-width, Q-rank-width and mim-width. For tree-width and clique-width, we even know algorithms that are optimal under SETH. However, these algorithms rely on techniques that are specific to each width parameter.
We unify these algorithmic results with a new notion of representativity between sets of partial colorings. This notion can be used to reduce the size of a collection of partial colorings in any dynamic programming algorithms for Graph Coloring. We give two applications of this new concepts:
- A meta-algorithm for q-Coloring whose running time asymptotically matches the runing time of the best-known algorithms for several width measures including clique-width, (Q-)rank-width and mim-width. Moreover, for clique-width and (Q-)rank-width, the performance of this meta-algorithm matches asymptotically the state of the art both in the few-colors and many-colors cases.
- A greedy algorithm that, given a branch decomposition of mim-width 1, solves Graph Coloring in quadratic time. Prior to our results, it was known that Graph Coloring was solvable in polynomial time on graphs of mim-width 1 (because they are perfect graphs) and NP-hard given a decomposition of mim-width 2.
Finally, we provide an interesting open question on the computation of representative sets of minimum size.
Time and date: 27/01/2021 at 14:30 (Paris time)