Monday, February 15, 2021

Talks in 2021


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.


Previous talks

Date and Time: May 27, 2021 at 17:00 hours Bergen time (GMT+2)
Speaker: Tuukka Korhonen, University of Helsinki
Title: Single-Exponential Time 2-Approximation Algorithm for Treewidth
Abstract: We give an algorithm, which given an n-vertex graph G and an integer k, in time 2^O(k) n either outputs a tree decomposition of G of width at most 2k + 1 or determines that the treewidth of G is larger than k. The previous best approximation ratio in time 2^O(k) n was 5, and in time 2^O(k) n^O(1) was 3, both given by Bodlaender et al. [SICOMP '16]. Our algorithm is based on a proof of Bellenbaum and Diestel [Comb. Probab. Comput. '02].

Date and Time: May 20, 2021 at 17:00 hours Bergen time (GMT+2)
Speaker: Michal Wlodarczyk, Eindhoven University of Technology
Title: Vertex Deletion Parameterized by Elimination Distance and Even Less
Abstract: We study the parameterized complexity of various classic vertex deletion problems such as Odd cycle transversal, Vertex planarization, and Chordal vertex deletion under hybrid parameterizations. Existing FPT algorithms for these problems either focus on the parameterization by solution size, detecting solutions of size k in time  f(k)*n^O(1), or width parameterizations, finding arbitrarily large optimal solutions in time f(w)*n^O(1) for some width measure w like treewidth. We unify these lines of research by presenting FPT algorithms for parameterizations that can simultaneously be arbitrarily much smaller than the solution size and the treewidth.

We consider two recently introduced classes of parameterizations which are relaxations of either treedepth of treewidth. They are related to graph decompositions in which subgraphs that belong to a target class H (e.g., bipartite or planar) are considered simple. First, we present a framework for computing approximately optimal decompositions for miscellaneous classes H. Namely, if the cost of an optimal decomposition is k, we show how to find a decomposition of cost k^O(1) in time f(k)*n^O(1). Secondly, we exploit the constructed decompositions for solving vertex-deletion problems under the new parameterizations.

Joint work with Bart M. P. Jansen and Jari J. H. de Kroon. 

Date and Time: May 13, 2021 at 17:00 hours Bergen time (GMT+2)
Speaker: Dimitrios M. Thilikos, LIRMM, Univ Montpellier, CNRS
Title: Parameterized Algorithms for Vertex Deletion to Minor-closed Graph Classes
Abstract: Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a {\em $k$-apex} of ${\cal G}$ if  $G$ contains a  set $S$ of at most $k$ vertices such that  $G\setminus S$ belongs to ${\cal G}$. We denote by ${\cal A}_k ({\cal G})$ the set of all graphs that are $k$-apices of ${\cal G}.$ In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${\cal A}_k ({\cal G})$, i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}).$ We design an algorithm that,  given a graph $G$  on $n$ vertices, runs in time $2^{{\sf poly}(k)}\cdot n^3$ and either returns a set $S$ certifying that $G \in {\cal A}_k ({\cal G})$,  or reports that $G \notin {\cal A}_k ({\cal G})$. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$ excludes some apex graph as a minor,  we give an alternative  algorithm running in  $2^{{\sf poly}(k)}\cdot n^2$-time.

Date and Time: May 06, 2021 at 17:00 hours Bergen time (GMT+2)
Speaker: Sebastian SiebertzUniversity of Bremen
Title: Twinwidth and Permutations
Abstract: Twin-width is a structural width measure that was recently introduced by Bonnet, Kim, Thomassé and Watrigant. We study the logical properties of twin-width and prove that a class of binary relational structures (edge-coloured partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class.
Joint work with Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez and Stéphan Thomassé.

Date and Time: April 08, 2021 at 17:00 hours Bergen time (GMT+2)
Speaker: Eduard Eiben, Royal Holloway University of London
Title: Removing Connected Obstacles in the Plane is FPT
Abstract: Given two points in the plane, a set of obstacles defined by closed curves, and an integer k, does there exist a path between the two designated points intersecting at most k of the obstacles? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory, wireless computing, and motion planning. It remains NP-hard even when the obstacles are very simple geometric shapes (e.g., unit-length line segments).
In this talk, we show that the problem is fixed-parameter tractable (FPT) parameterized by k, by giving an algorithm with running time $k^{O(k^3)}n^{O(1)}$. Here n is the number connected areas in the plane drawing of all the obstacles.

Date and Time: March 25, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Sitan Chen, Massachusetts Institute of Technology
Title: Learning Deep ReLU Networks is Fixed-Parameter Tractable
Abstract:  We consider the problem of learning an unknown ReLU network with an arbitrary number of layers under Gaussian inputs and obtain the first nontrivial results for networks of depth more than two. We give an algorithm whose running time is a fixed polynomial in the ambient dimension and some (exponentially large) function of only the network's parameters. These results provably cannot be obtained using gradient-based methods and give the first example of a class of efficiently learnable neural networks that gradient descent will fail to learn. In contrast, prior work for learning networks of depth three or higher requires exponential time in the ambient dimension, while prior work for the depth-two case requires well-conditioned weights and/or positive coefficients to obtain efficient run-times. Our algorithm does not require these assumptions. Our main technical tool is a type of filtered PCA that can be used to iteratively recover an approximate basis for the subspace spanned by the hidden units in the first layer. Our analysis leverages properties of lattice polynomials from tropical geometry. Based on joint work with Adam Klivans and Raghu Meka.

Date and Time: March 18, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: S\'andor Kisfaludi-Bak, Max Planck Institute for Informatics
Title: Planar Steiner Tree With Terminals On Few Faces
Abstract: 
In the Steiner tree problem, we are given a graph and a set S of vertices (terminals), and the goal is to find the shortest tree T containing S. The problem is often studied with the number of terminals (|S|) as parameter, for which it is fixed-parameter tractable. The problem is also well-studied in planar graphs. Interestingly, if all terminals are on the outer face of a plane graph, then Steiner tree is polynomial-time solvable, which motivates a parameter smaller than |S|: let k be the minimum number of faces in the plane graph that can cover S. We will discuss how we can go beyond the natural n^O(k) algorithm to obtain a running time of 2^O(k) * n^O(sqrt(k)). On the other hand, we will see some of the main ideas of a reduction that yield a lower bound of n^Omega(sqrt(k)) under the Exponential Time Hypothesis, which nearly matches the running time, and also proves W[1]-hardness for this parameter. The talk is based on joint work with Jesper Nederlof and Erik Jan van Leeuwen.


Date and Time: March 11, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Fahad Panolan, Indian Institute of Technology Hyderabad
Title: Hitting topological minors is FPT
Abstract: In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G, a family of undirected graphs F, and an integer k. The task is to determine whether G contains a set S of vertices of size at most k, such that the graph G-S contains no graph from F as a topological minor. We give an algorithm for TM-Deletion with running time f(h,k) poly(|V(G)|), where h is the maximum size of a graph in F, and f  is a computable function of h and k. This is the first fixed-parameter tractable algorithm (FPT) for the problem. 

This is joint work with Fedor V. Fomin, Daniel Lokshtanov, Saker Saurabh, and Meirav Zehavi. 

Date and Time: March 04, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Danil Sagunov, Steklov Institute of Mathematics
Title: Algorithmic Extensions of Dirac's Theorem
Abstract: The Dirac's Theorem states that every n-vertex 2-connected graph contains a cycle twice as long as its minimum degree. This bound is tight and the corresponding cycle can be found in polynomial time following Dirac's original proof. Moreover, the problem of finding a cycle whose length is at least (2+eps) times minimum degree is NP-hard for any constant eps > 0. 

We study the problem of finding a cycle slightly longer than the bound of the Dirac's theorem in a 2-connected graph, i.e. a cycle of length at least twice its minimum degree plus k. Using several known and new methods and constructions, we show that this problem is solvable in FPT time with single-exponential dependence on k. Interestingly, for obtaining such an algorithm, we design algorithms for several related parameterized problems. Prior to this work, parameterized complexity of some of them was questioned and remained unresolved in the literature. Apart from that, the proof builds on a new graph-theoretical result that is interesting on its own. 

In this talk, we will discuss the main points of the central result of this work, its main constructions and ideas, and directions of the future research. 

This is joint work with Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov.

Date and Time: February 25, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Bart Jansen, Eindhoven University of Technology
Title: Algebraic Sparsification for Decision and Maximization Constraint Satisfaction Problems
Abstract: We survey polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language), and how sparsification algorithms can be obtained by modeling constraints as low-degree polynomials. We also consider the corresponding problem for Maximum CSP problems, where the notion of characteristic polynomials turns out to characterize optimal compressibility.

Based on joint work with Hubie Chen, Astrid Pieterse, and Michal Wlodarczyk

Date and Time: February 18, 2021 at 17:00 hours Bergen time (GMT+1)
Speaker: Magnus Wahlstr\"om, Royal Holloway University of London
Title: Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
Abstract: We show the existence of so-called mimicking networks of k^O(log k) edges, mimicking the behaviour of multicuts over a set of terminals of total capacity k.  We also show an efficient (randomized) construction that produces such a network with k^O(log^3 k) edges, using an approximation algorithm for Small Set Expansion. This improves on a recent result (W., ICALP 2020), which showed only the existence.

As a consequence, a range of problems have quasipolynomial kernels, in particular including Edge Multiway Cut, Group Feedback Edge Set and Subset Feedback Edge Set (in its general formulation, with undeletable edges). The existence of a polynomial kernel for Multiway Cut is one of the biggest open questions in kernelization, and this result is the first improvement in general graphs since the introduction of the representative sets approach to kernelization in 2012 (Kratsch and W.).

The talk assumes no previous knowledge of matroids or other previous work on the problem.


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


December 10, 2020

  • Parinya ChalermsookAalto University
  • Title: Vertex Sparsification for Edge Connectivity
  • Abstract: Graph compression is a basic information theoretic and computational question that has found its applications in many areas of algorithm design. In this work, we initiate the study of a parameterized variant of graph compression that preserves cut sizes between designated terminals. We present applications in designing fast dynamic graph algorithms and in the survivable network design problems in low treewidth graphs. 
           (Joint work with Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, Danial Vaz.)


November 26, 2020

  • Karol Węgrzycki, Saarland University and Max Planck Institute for Informatics
  • Title: Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
  • Abstract: We present an O*(2^{0.5 n}) time and O*(2^{0.249999n}) space randomized algorithm for Subset Sum. This is the first improvement over the long-standing O*(2^{n/2}) time and O*(2^{n /4}) space algorithm due to Schroeppel and Shamir. This talk will also feature an introduction to the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016) and representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010). Finally, we will uncover a tight and curious relation between the Subset Sum and Orthogonal Vectors problem. 
         This is joint work with Jesper Nederlof (Utrecht University). 

         Full version: https://arxiv.org/abs/2010.08576


November 12, 2020

  • Karthik ChandrasekaranUniversity of Illinois, Urbana-Champaign
  • Title: Hypergraph k-cut for fixed k in deterministic polynomial time
  • Abstract: In the hypergraph k-cut problem, the input is a hypergraph along with a fixed constant k and the goal is to find a smallest subset of hyperedges whose removal ensures that the remaining hypergraph has at least k connected components. The graph k-cut problem is solvable in polynomial time (Goldschmidt and Hochbaum, 1988) while the complexity of the hypergraph k-cut problem was open. In this talk, I will present the first deterministic polynomial-time algorithm to solve the hypergraph k-cut problem. Our algorithm relies on novel structural results that provide new insights even for the graph k-cut problem. 
          Based on joint work with Chandra Chekuri.

October 29, 2020

  • Ariel KulikComputer Science Department, Technion
  • Title: Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
  • Abstract: In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and 3-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random 1.5-approximation algorithm for Vertex Cover, whose running time of O*(1.01657k) substantially improves the best known running time of O*(1.0883k) [Brankovic and Fernau, 2013]. For 3-Hitting Set we present a parameterized random 2-approximation algorithm with running time of O*(1.0659k), improving the best known O*(1.29k) algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations. We show an equivalence between these recurrences and a stochastic process, which we analyze using the Method of Types, by introducing an adaptation of Sanov’s theorem to our setting. We believe our novel analysis of recurrence relations, which is of independent interest, is a main contribution of this paper.

October 15, 2020

  • William LochetUniversity 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

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

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/