# Frontiers of Parameterized Complexity

A blog for parameterized complexity community

## Friday, May 1, 2020

### Next talk

####
**May 28, 2020 17:00 Bergen time (GMT+2)**

####
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.

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.

####

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.

####
The recordings of the previous talks are now available on our YouTube channel 'Frontiers of Parameterized Complexity' https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA/

## Sunday, April 12, 2020

### Talks schedule

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

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.

On a high level, our approach is via a new problem called the MINHAMPAIR problem: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MINHAMPAIR based on a new sparse cut-based factorization of the `matchings connectivity matrix', introduced by Cygan et al. [JACM'18].

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

####

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.

The slides of the talk are available here.

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.

**April 23, 2020**Utrecht University**Jesper Nederlof,****Title:**Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication**Abstract:**

On a high level, our approach is via a new problem called the MINHAMPAIR problem: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MINHAMPAIR based on a new sparse cut-based factorization of the `matchings connectivity matrix', introduced by Cygan et al. [JACM'18].

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

**April 30, 2020**, UCSB__Daniel Lokshtano____v__**Title**:**Abstract**:

####
In the Min k-Cut problem, input is an edge weighted graph G and an integer k, and the task is to partition the vertex set into k non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta {\em et al.} [SODA 2018] initiated the study of FPT-approximation for the Min k-Cut problem and gave an 1.9997-approximation algorithm running in time 2^{O(k^6}n^{O(1)}. Later, the same set of authors~[FOCS 2018] designed an (1 +\epsilon)-approximation algorithm that runs in time (k/\epsilon)^{O(k)}n^{k+O(1)}, and a 1.81-approximation algorithm running in time 2^{O(k^2)}n^{O(1)}. More, recently, Kawarabayashi and Lin~[SODA 2020] gave a (5/3 + \epsilon)-approximation for Min k-Cut running in time 2^{O(k^2 \log k)}n^{O(1)}.

In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (\ETH) and constants in the exponent). In particular, for every \epsilon > 0, the algorithm obtains a (1 +\epsilon)-approximate solution in time (k/\epsilon)^{O(k)}n^{O(1)}. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s^{O(k)}n^{O(1)} on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The later two are of independent interest.

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

**May 7, 2020**

In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (\ETH) and constants in the exponent). In particular, for every \epsilon > 0, the algorithm obtains a (1 +\epsilon)-approximate solution in time (k/\epsilon)^{O(k)}n^{O(1)}. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s^{O(k)}n^{O(1)} on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The later two are of independent interest.

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

**May 7, 2020**

, CMU__Jason Li__**Title**:**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.

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

#### May 14, 2020

, Google Zürich__Vincent Cohen-Addad__**Title**:**Abstract**:

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 21, 2020

**Michal Pilipczuk,**University of Warsaw**Title**:**Abstract**:

The slides of the talk are available here.

#### May 28, 2020

**Daniel Marx,**Max-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)

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.

#### June 04, 2020

**Hans Bodlaender,**Utrecht 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.)**

#### June 11, 2020

**Edith Elkind,**University of Oxford**Title: tba****Abstract**:

#### 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.)

## Saturday, April 11, 2020

**YouTube channel Frontiers of Parameterized Complexity**https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA/

Subscribe to:
Posts (Atom)