## Friday, June 26, 2020

### Frontiers of PC 2.0

#### Thank you for tuning on with us so far. We break now for a short summer break and revive the talks again in August 2020. Wishing you all a happy summer break!

The recordings of the previous talks are available on our YouTube channel 'Frontiers of Parameterized Complexity'. The links to the available slides of the past talks can be found after their abstracts in this blog.

## Sunday, April 12, 2020

### Talks schedule

By default, the talks start at 17:00 Bergen time (GMT+1)

Link to the zoom meeting: https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: name of the W[1]-complete problem, 6 letters, all capital. Also known as a set of pairwise adjacent vertices.

#### October 15, 2020

• University of Bergen
• Title: A polynomial time algorithm for the $k$-disjoint shortest path problem
• Abstract: The disjoint paths problem is a fundamental problem in algorithmic graph theory. For a given graph $G$ and a set of $k$ pairs of terminals in $G$, it asks for the existence of $k$ vertex-disjoint paths connecting each pair of terminals. Very famously, Robertson and Seymour proved the existence of a $n^3$ algorithm for any fixed $k$ in 1995 as part of the Graph Minor project. In this talk, we focus on the version of this problem where all the paths are required to be shortest paths. This was first introduced as the disjoint shortest paths problem by Eilam-Tzoreff in 1998 where she proved that the case $k = 2$ admits a polynomial time algorithm. She also asked for the existence of a polynomial time algorithm for any fixed $k$, a question which remained open even for the case $k = 3$. The goal of this talk is to prove that, for any fixed $k$, there exists a $n^{f(k)}$ algorithm for the $k$-disjoint shortest paths problem, answering Eilam-Tzoreff's question.

#### October 01, 2020

• Universite Claude Bernard Lyon
• Title: Twin-width
• Abstract: Inspired by an 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, $K_t$-free unit ball graphs, posets with bounded-size antichains, proper subclasses of permutation graphs, and some cubic expanders based on repeated 2-lifts, all have bounded twin-width. On all these classes we can compute in polynomial time a d-contraction sequence, witness that the twin-width is at most d. FO model checking asks if a given first-order sentence $\phi$ is true on a given structure G. We show that this problem is FPT in parameter $|\phi|$ on classes of bounded twin-width binary structures, provided the witness is given. More precisely, given a d-contraction sequence for G, our algorithm runs in time $f(d,|\phi|) |V(G)|$ where f is a computable but non-elementary function. Practical algorithms do exist for typical FO expressible problems, like k-Independent Set and k-Dominating Set. Furthermore twin-width is robust as far as first-order logic is concerned: any transduction of a bounded twin-width class has bounded twin-width. Bounded twin-width classes have other interesting properties: they are small, $\chi$-bounded, satisfy the strong Erdos-Hajnal property, and their intersection with the sparse world has many equivalent characterizations.

We will survey our current understanding of twin-width, putting the emphasis on fixed-parameter tractability of FO model checking and intriguing/pressing open questions.

This is joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.

#### September 17, 2020

• Meirav Zehavi, Ben-Gurion University
• Title: Lossy Kernelization for (Implicit) Hitting Set Problems
• Abstract:
We re-visit the complexity of polynomial time pre-processing (kernelization) for the $d$-Hitting Set problem, one of the classic problems in Parameterized Complexity. This problem encompasses a number of fundamental parameterized problems: Vertex Cover, as well as special cases of 3-Hitting set, namely Feedback Vertex in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, this implies polynomial kernels to deletion to any hereditary property that can be characterized by a finite set of forbidden induced  subgraphs. With respect to bit size the kernelization complexity of $d$-Hitting Set is essentially settled: there exists a kernel with $O(k^d)$ bits ($O(k^d)$ sets and $O(k^{d-1})$ elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. On the other hand, it is a major open problem in the field to determine whether there exists a kernel for $d$-Hitting Set with fewer elements.

We show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed $d$.  Further, we show that there exist approximate Turing kernelizations for $d$-Hitting Set that even beat the established bit size lower bounds for exact kernelizations---in fact, we use a constant number of oracle calls, each with near linear'' ($O(k^{1+\epsilon})$) bit size. For two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the best of both worlds'' type of results---$(1+\epsilon)$-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.  On the way, we use an interesting fact about the natural Linear Programming (LP) relaxation of $d$-Hitting Set: there exists a set $S$ of at most $k\cdot d$ elements that contains the support of every optimum LP solution to the LP-relaxation of $d$-Hitting Set.

#### September 10, 2020

• Peter Gartland, University of California Santa Barbara
• Title: Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
• Abstract:
We present an algorithm that takes as input a graph G with weights on the vertices, and computes a maximum weight independent set S of G. If the input graph G excludes a path P_k on k vertices as an induced subgraph, the algorithm runs in time n^{O((k^2)log^3 n)}. Hence, for every fixed k our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomasse, SODA'20 invited presentation]. Previous to this work, polynomial time algorithms were only known for P_4-free graphs [Corneil et al., DAM'81], P_5-free graphs [Lokshtanov et al., SODA'14], and P_6-free graphs [Grzesik et al., SODA'19]. For larger values of t, only 2^{O(sqrt{knlog n})} time algorithms [Bacso et al., Algorithmica'19] and quasi-polynomial time approximation schemes [Chudnovsky et al., SODA'20] were known. Thus, our work is the first to offer conclusive evidence that Independent Set on P_k-free graphs is not NP-complete for any integer k.

#### Karthik C.S., Tel Aviv UniversityTitle: Towards a Unified Framework for Hardness of Approximation in PAbstract: Currently there are two popular techniques to create a gap and prove fine-grained/fixed-parameter inapproximability results in P. One is the Distributed PCP framework established by Abboud, Rubinstein, and Williams (2017), and the other is the Threshold Composition technique introduced by Lin (2015). In this talk we will survey results proved using these two techniques and also explore the connections between them.The recording of this talk is now available at https://www.youtube.com/watch?v=Pn9OlmF008Q.August 20, 2020Pasin Manurangsi, Google ResearchTitle: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic NoiseAbstract: We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution -independent agnostic PAC model, with a focus on $L_p$ perturbations. We give a computationally efficient learning algorithm and a nearly matching running time lower bound for this problem. An interesting implication of our findings is that the $L_{\infty}$ perturbations case is provably computationally harder than the case $2 \leq p < \infty$. Specifically, when parameterized by the margin, the former is not FPT whereas the latter is. . Based on joint work with Ilias Diakonikolas and Daniel M. Kane.

The recording of this talk is now available at https://www.youtube.com/watch?v=QLik4RZ-ew4. The slides of the talk are available here.

#### August 13, 2020

• Kevin Prattt, Carnegie Mellon University
• Title: Parameterized applications of multivariate polynomial differentiation
• Abstract:
The apolar inner product of two polynomials over a field is defined as the dot product of their coefficient vectors (with appropriate scaling). Specific instances of computing this inner product lead to the fastest-known algorithms for several intractable problems, including computing the permanent of a matrix and detecting simple paths in a graph. In this talk I will explore two different approaches for computing this inner product, one numeric and one symbolic. I will show how these yield in a very general manner non-trivial algorithms for problems such as detecting and approximately counting simple paths in a graph. Our approaches raise concrete algebraic questions that could provide a path to faster algorithms for these (and other) problems.

Part of this talk is based on joint work with Cornelius Brand.

The recording of the talk is now availbale at https://www.youtube.com/watch?v=qAEazQQ6dK8.

#### June 25, 2020

• Marcin Pilipczuk, University of Warsaw
• Title: Optimal Discretization is Fixed-parameter Tractable
• Abstract:
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W_1 from W_2, that is, in every region into which the lines partition the plane there are either only points of W_1, or only points of W_2, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of x-coordinates and the range of y-coordinates into as few segments as possible, maintaining that no pair of points from W_1 \times W_2 are projected onto the same pair of segments under this discretization.

We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time 2^O(k^2 log k) n^O(1), where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.

(Joint work with Stefan Kratsch, Toma\v{s} Masa\v{r}ik, Irene Muzi, Manuel Sorge.)

The recording of this talk is now available at https://www.youtube.com/watch?v=y8ab7XfqvMg.

June 18, 2020
• Martin Grohe, RWTH Aachen University
• Title: Polylogarithmic Parameterized Algorithms for the Graph Isomorphism Problem: From Bounded Degree to Excluded Minors
• Abstract:
Building on Babai's quasipolynomial graph isomorphism test, we designed a number of parameterized isomorphism tests that exhibit an unusual running time that is quasipolynomial in the parameter (that is, n^{polylog(k)}). The first parameter for which we could find such an algorithm is the maximum degree, the latest the Hadwiger number, that is, the maximum h such that K_h is a minor.

In this talk, I'll give a high level introduction into the techniques used in these algorithms. (Joint work with Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking.)

The recording of this talk is now available at https://www.youtube.com/watch?v=6WODAEleYBw.

#### June 11, 2020

• Edith ElkindUniversity of Oxford
• Title: Hedonic diversity games
• Abstract:
We consider a setting where players belong to two types (men and women, vegetarians and carnivores, junior and senior researchers) and need to split into groups, with each player having preferences over the proportion of the two player types in his or her group. We study the problem of finding a stable partition, for several game-theoretic notions of stability; while some of the problems we consider turn out to be polynomial-time solvable, others are NP-hard, in which case we also explore their parameterized complexity.

Based on joint work with Ayumi Igarashi, Robert Bredereck and Niclas Boehmer.

The recording of this talk is now available at https://www.youtube.com/watch?v=zzmk0R_thF4. The slides of the talk are available here. There was an error on slide 13 of the presentation, which is corrected in the updated slides: for dichotomous diversity games an outcome in the core always exists and can be found in polynomial time. The proof can be found in the MSc thesis of Nicolas Boehmer.

#### June 04, 2020

• Hans BodlaenderUtrecht University
• Title: Typical Sequences Revisited - Computing Width Parameters of Graphs
• Abstract:
In this talk, we revisit a key element of the currently asymptotic fasters parameterized algorithms for treewidth and pathwidth: typical sequences.These were introduced in 1991, by Lagergren and Arnborg, and independently by Bodlaender and Kloks. We give a structural result on thejoin of typical sequences, which speeds up one step in these algorithms for treewidth and pathwidth, but does not yet give better time bounds. The result is used to obtain polynomial time algorithms for some problems on directed series parallel graphs. The talk also discusses the current (open) status of the parameterized complexity of pathwidth and treewidth. (This is  a joint work with Lars Jaffke and Jan Arne Telle.)

The recording of this talk is now available at https://www.youtube.com/watch?v=uVr3wVxmYL4.  The slides of the talk are available here.

#### May 28, 2020

• Daniel MarxMax-Planck-Institut für Informatik
• Title: Incompressibility of H-free edge modification problems: Towards  dichotomy
• Abstract:
Given a graph G and an integer k, the H-free Edge Editing problem is to find whether there exists at most k pairs of vertices in G such that changing the adjacency of the pairs in G results in a graph without any induced copy of H. The existence of polynomial kernels for H-free Edge Editing received significant attention in the parameterised complexity literature. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices, but starting from 5 vertices, polynomial kernels are known only if H is either complete or empty. This suggests the conjecture that there is no H with at least 5 vertices where H-free Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set of nine 5-vertex graphs such that if H-free Edge Editing is incompressible for every H in this set, then H-free Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty (under the usual complexity assumptions). That is, proving incompressibility for these nine graphs would give a complete classification of the kernelization complexity of H-free Edge Editing for every H with at least 5 vertices.

We obtain similar result also for H-free Edge Deletion. Here the picture is more complicated due to the existence of another infinite family of graphs H where the problem is trivial (graphs with exactly one edge). We obtain a larger set of 19 graphs whose incompressibility would give a complete classification of the kernelization complexity of H-free Edge Deletion for every graph H with at least 5 vertices. Analogous results follow also for the H-free Edge Completion problem by simple complementation.

(Joint Work with R. B. Sandeep)

The recording of this talk is now available at https://www.youtube.com/watch?v=MAD5IR6mT-A. The slides of the talk are available here.

#### May 21, 2020

The last decade has witnessed impressive progress on the understanding of structure in sparse graphs. Much of this progress can be attributed to the systematic exploration of abstract definitions of structural sparsity --- concepts of bounded expansion and nowhere denseness. From the parameterized perspective, these two notions have brought new techniques to the toolbox and helped to explain the parameterized complexity of problems definable in First Order logic. However, the contemporary graph theory offers multiple quantitative notions (aka parameters) of "well-structuredness" that reach beyond sparse graphs. To name just a few, we may bound the rankwidth of a graph, exclude a vertex-minor, or stipulate VC parameters like VC dimension or VC density. In the talk we will survey the recent advances in lifting the developments of sparsity to classes of well-structured dense graphs. We will particularly focus on connections with concepts from model theory: stable and NIP classes, and the notion of FO transductions.

The recording of this talk is now available at https://www.youtube.com/watch?v=JHjh3u4ZUWo. The slides of the talk are available here.

#### May 14, 2020

• Title: On the Parameterized Complexity of Various Clustering Problems
• Abstract:
Clustering problems are fundamental computational problems. On the one hand they are at the heart of various data analysis, bioinformatics or machine learning approaches, on the other hand, they can be seen as variants of 'set cover' problems (involving e.g. metrics, graphs with a special structure, etc.) and so are very basic problems.
For many applications, finding efficient fixed-parameter algorithms is a very natural approach. Popular choices of parameters are either parameters of the problem itself (e.g. the number of clusters) or on the underlying structure of the input (e.g. the dimension in the metric case). We will focus on classic metric clustering objectives such as k-median and k-means and review recent results on the fixed parameter complexity of these problems, and the most important open problems.

The recording of this talk is now available at https://www.youtube.com/watch?v=Fgh-20qHzfg. The slides of the talk are available here.

#### May 7, 2020

• Jason Li, CMU
• Title: Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Abstract:
In the Feedback Vertex Set problem, one is given an undirected graph $G$ and an integer $k$, and one needs to determine whether there exists a set of $k$ vertices that intersects all cycles of $G$ (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent test bed for many important algorithmic techniques in the field such as Iterative Compression~[Guo et al. (JCSS'06)], Randomized Branching~[Becker et al. (J. Artif. Intell. Res'00)] and Cut\&Count~[Cygan et al. (FOCS'11)].
In particular, there has been a long race for the smallest dependence $f(k)$ in run times of the type $O^\star(f(k))$, where the $O^\star$ notation omits factors polynomial in $n$. This race seemed to be run in 2011, when a randomized $O^\star(3^k)$ time algorithm based on Cut\&Count was introduced.
In this work, we show the contrary and give a $O^\star(2.7^k)$ time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size $k$ of bounded average degree, a tree decomposition of width $(1-\Omega(1))k$ can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from~[Becker et al. (J. Artif. Intell. Res'00)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.

The recording of this talk is now available at https://www.youtube.com/watch?v=mhyS7cqYoYw.

April 30, 2020

• Daniel Lokshtanov, UCSB
• Title: A Parameterized Approximation Scheme for Min k-Cut
• Abstract:

## Saturday, April 11, 2020

This blog contains the list of talks on Frontiers of Parameterized Complexity. The initial plan to have talks every week, on Thursdays, at 17.00 Bergen time (GMT+2). The recordings of the talks have be found at our YouTube channel Frontiers of Parameterized Complexity https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA/