Monday, August 3, 2020

Next Talk

We are back with our online seminar series on Frontiers of Parameterized Complexity. As before we have talks every Thursday at 17:00 GMT+2

Henceforth, the talks will be scheduled once every two weeks on Thursdays at 17:00 GMT+2. Stay tuned for the announcement of the next talk.
 
The details for joining the talk are given below.
The link to join the zoom talk is https://uib.zoom.us/j/4231169675.

Meeting ID: 423 116 9675
Password: Name of the W[1]-complete problem, six letters, all capital. Set of pairwise adjacent vertices.

Date and Time: TBA
Speaker: TBA
Title: TBA
Abstract: TBA

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!


To get notifications about the next talks via email please send an email to rsharma@mpi-inf.mpg.de with the subject line 'Subscribe FrontPC' (if you haven't already). For more information, please contact any one of the following: Fedor Fomin (Fedor.Fomin@uib.no), Saket Saurabh (saket@imsc.res.in), Roohani Sharma (rsharma@mpi-inf.mpg.de).

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.

Thursday, May 7, 2020

YouTube channel

Missed out on your favourite talks? 

Catch them up at our YouTube channel 'Frontiers of Parameterized Complexityhttps://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.

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.

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

September 03, 2020

August 27, 2020

  • Karthik C.S., Tel Aviv University
  • Title: Towards a Unified Framework for Hardness of Approximation in P
  • Abstract: 
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, 2020

  • Pasin Manurangsi, Google Research
  • Title: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
  • Abstract: 
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

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

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.

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.

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/