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 Chalermsook, Aalto 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 Chandrasekaran, University 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 Kulik, Computer 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 Lochet, 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
- Edouard Bonnet, 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.
The recording of this talk is now available at https://www.youtube.com/watch?v=RldGIFoJHtY.
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 Elkind, University 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 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.)
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 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)
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.
- 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.
