Thursday, May 7, 2020

Missed out on your favourite talks? 

Catch them up at our YouTube channel 'Frontiers of Parameterized Complexity' https://www.youtube.com/channel/UCdfML-PShQNSCeqbz9Ol_oA/



Friday, May 1, 2020

Next talk

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


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)

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.

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.

April 23, 2020
  • Jesper Nederlof, Utrecht University
  • Title: Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication
  • Abstract:   
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n^2*2^n) time. Since then it has been a notorious problem to improve the runtime to O((2-eps)^n) for some constant eps >0. In this work we establish the following progress: If (s x s)-matrices can be multiplied in s^{2+o(1)} time, than all instances of TSP in bipartite graphs can be solved in O(1.9999^n) time by a randomized algorithm with constant error probability.  We also indicate how our methods may be useful to solve TSP in non-bipartite graphs.

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
  • Daniel Lokshtanov, UCSB 
  • Title: A Parameterized Approximation Scheme for Min k-Cut
  • 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

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

May 14, 2020

  • Vincent Cohen-Addad, Google Zürich
  • 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 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 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)

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

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/