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 Siebertz, University 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.