The link to join the zoom talk is https://uib.zoom.us/j/

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.

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

**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).

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

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

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

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