Benjamin Bergougnoux

Exploiting Triadic Closure Algorithmically The triadic closure principle postulates that vertices with many common neighbors are likely to be adjacent themselves. To model this principle graph-theoretically, Fox et al. [SICOMP ’20] introduced the parameter \(c\)-Closure for undirected graphs. The parameter is defined as the largest number \(c\) such that every pair of nonadjacent vertices has at most \(c-1\) common neighbors. In this talk, I will discuss some properties of \(c\)-closed graphs and survey some recent algorithmic results that make use… Read More »Wednesday 10:30 – Christian Komusiewicz

Disjoint paths on dense graphs In this talk we will see the proof that the \(k\) edge disjoint paths problem can be solved in polynomial time on graphs with minimum degree \(\alpha \cdot n\) provided \(k\) is small enough (but still linear in \(n\)). In particular this implies a linear kernel on the class of graphs with linear minimum degree, which is not possible on general graphs. This is based on a joint work with Lokshtanov, Saurabh and Zehavi that… Read More »Tuesday 16:30 – William Lochet

SAT Backdoors: Depth Beats Size For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather… Read More »Tuesday 16:00 – Sebastian Ordyniak

A Meta-Theorem for Distributed Certification Distributed certification deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and… Read More »Tuesday 12:00 – Ioan Todinca

A characterization of graphs with (quasi)-polynomial many minimal separators A class \(F\) is called tame if for every \(n\)-vertex graph \(G\) in \(F\), \(G\) has at most \(n^{O(1)}\) minimal separators, \(F\) is called quasi-tame if for every \(n\)-vertex graph \(G\) in \(F\), \(G\) has at most \(n^{O(polylog(n))}\) minimal separators, and \(F\) is called feral if there exists a constant \(c > 1\) such that for arbitrarily large \(n\), \(F\) contains an \(n\)-vertex graph \(G\) that has at least \(c^n\) minimal… Read More »Tuesday 11:30 – Peter Gartland

Deletion and Elimination to Hereditary Graph classes Vertex-deletion problems have been at the heart of parameterized complexity throughout its history where the most commonly used parameter is the size of the modulator (deletion set). Recent years there have been attempts to measure the modulator in ways other than the size which is significantly smaller than the size of the modulator. In 2016, Bulian and Dawar introduced elimination distance to a graph class \(H\). In this talk we discuss elimination distance… Read More »Tuesday 10:30 – Fahad Panolan

Tight bounds for counting colorings and connected edge sets parameterized by cutwidth. Tight bounds for counting colorings and connected edge sets parameterized by cutwidth. We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small edge separators. Let \(p,q \in \mathbb{N}\) such that p is… Read More »Monday 12:00 – Jesper Nederlof

The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width The generic homomorphism problem, which asks whether an input graph \(G\) admits a homomorphism into a fixed target graph \(H\), has been widely studied in the literature. We provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of \(G\) for virtually all choices of \(H\) under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature… Read More »Monday 11:30 – Kirill Simonov

Search-Space Reduction Beyond Kernelization The framework of kernelization gives a mathematical model for the rigorous analysis of preprocessing, aimed at showing that any instance with parameter k can efficiently be reduced to an equivalent one whose size depends only on \(k\). Kernelization serves as a useful tool to obtain FPT algorithms, since any brute-force algorithm solves the reduced instance in time depending only on \(k\). However, from the definition of kernelization it is not clear why kernelization would lead to… Read More »Thursday 9:30 – Bart Jansen

A Compound Logic for Modification Problems: Big Kingdoms Fall from Within We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator… Read More »Wednesday 9:30 – Dimitrios Thilikos