On May 12, 2020, Eun Jung Kim (김은정) from LAMSADE, CNRS presented a talk on her recent work on the twin-width. The title of her talk was “Twin-width: tractable FO model checking“. She is visiting the IBS discrete mathematics group from May 12 for about 4 months.
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA ’14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15].
In order to explore the limits of twin-width, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e., they contain at most $n! c^n$ graphs on $n$ vertices, for some constant $c$). This implies by a counting argument that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width.
Eun Jung Kim (김은정) from LAMSADE, CNRS, Paris gave a talk at Discrete Math Seminar on January 4, 2019. The title of her talk was “New algorithm for multiway cut guided by strong min-max duality”.
Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design.
In this talk, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds, namely μ(I)=2LP(I)-IP(dual-I). Here, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations, where k is the budget for a solution.
This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.