Celebrating Michael R. Fellows' 65th Birthday

It will be happening at the University of Bergen, Norway!

15th and 16th of June, 2017

More Info

In case you don't know Mike

Here's what Wikipedia has to say about him

Here's what the University of Bergen has to say

And you can also check his personal page for more info

Meet the speakers

Hubert Chan

The University of Hong Kong
Hong Kong

Fedor Fomin

University of Bergen
Bergen, Norway

Petr Golovach

University of Bergen
Bergen, Norway

Bart Jansen

Eindhoven University of Technology
The Netherlands

Mamadou Kanté

Université Blaise Pascal
Clermont-Ferrand, France

Daniel Lokshtanov

University of Bergen
Bergen, Norway

Amer Mouawad

University of Bergen
Bergen, Norway

Meirav Zehavi

University of Bergen
Bergen, Norway

Event Schedule

1:00pm to 1:15pm (209M3 Stort Auditorium)

Petter Bjorstad: Welcome

1:15pm to 2:00pm (209M3 Stort Auditorium)

Mamadou Kante: FPT algorithms parametrized by clique-width

Recently, many tight FPT algorithms parametrised by treewidth were proposed, but almost nothing for clique-width. I will propose in this talk an algorithm running in time n^O(k) for computing a Hamiltonian cycle in graphs of clique-width k, which is tight and answer a question posed by Fomin et al. in their SODA’10 paper. In order to obtain such a time complexity, we classify the partial solutions with respect to eulerian trails in some auxiliary graphs, the number of which is bounded by n^O(k). In a second part, I will show how we can modify the rank-based approach proposed by Bodlaender et al [ICALP’13] to propose a 2^O(k) time algorithm for computing a minimum feedback vertex set (and other connectivity constraints problem such as Connected Vertex Cover or Connected Dominating Set or Minimum Node-Steiner Tree).

2:15pm to 3:00pm (209M3 Stort Auditorium)

Fedor Fomin: Graph decompositions and algorithms

We overview the recent progress in solving intractable optimization problems on planar graphs as well as other classes of sparse graphs. In particular, we discuss how tools from Graph Minors theory can be used to obtain

  1. subexponential parameterized algorithms
  2. approximation algorithms, and
  3. preprocessing and kernelization algorithms on these classes of graphs.

3:00pm to 3:30pm

Coffee break

3:30pm to 4:15pm (209M3 Stort Auditorium)

Hubert Chan: Revisiting Diffusion Process for Hypergraph Laplacian

Hypergraph Laplacian has been defined via a diffusion process [Louis STOC 2015]. The spectral properties of the Laplacian is used to achieve a variant of the Cheeger's inequality for hyperedge expansion and higher-order Cheeger-like inequalities for multi-way expansion. In this talk, we take a closer look at this diffusion process, in which each hyperedge tries to transfer measure from vertices having maximum measure to those having minimum. In order for the diffusion process to be well-defined, we see that the hyperedges must be coordinated to essentially solve a densest subset problem. Consequently, we can recover the basic Cheeger's inequality, but higher-order spectral properties of the Laplacian do not hold in hypergraphs in general. This is joint work with Anand Louis, Zhihao Gavin Tang and Chenzi Zhang.

4:15pm to 5:00pm (209M3 Stort Auditorium)

Petr Golovach: Spanning problems in regular matroids

We consider the fundamental Matroid Theory problems of spanning a set T of given terminal elements. Specifically, we study the Space Cover and Minimum Spanning Circuit problems. In both problems, we are given a matriod M with a ground set E and a subset of its elements T. The task of Space Cover is to find a minimum set F \subseteq E disjoint with T such that the linear span of F contains all elements of T. Respectively, the task of Minimum Spanning Circuit is to find a minimum set F \subseteq T disjoint with T such that F \cup T is a circuit of M. For graphic matroids, these problems are equivalent to well-known graph problems: Space Cover is equivalent to the Steiner Forest problem and Minimum Spanning Circuit corresponds to the Cycle Through Elements problem. We investigate parameterized complexity of the problems on regular matroids, a superclass of graphic matroids.

  1. We give a parameterized algorithm for Space Cover with running time 2^{O(k)} . |E|^{O(1)}, where k is the size of F.
  2. We show that Minimum Spanning Circuit can be solved in time 2^{O(k^2\log k)} . |E|^{O(1)}.
Our algorithms exploit the classical decomposition theorem of Seymour for regular matroids. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely as the problems parameterized by k are W[1]-hard on binary matroids even when |T| = 1. The talk is based on the joint work with Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.

12:00pm to 1:00pm (3rd floor library)

Lunch

1:00pm to 1:15pm (209M3 Stort Auditorium)

Frances Rosamond: Welcome

1:15pm to 2:00pm (209M3 Stort Auditorium)

Daniel Lokshtanov: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, the probability that X is a subset of Y is roughly 1 / [(d+1)k choose k]. The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G, a set T = [{s_1, t_1}, {s_2, t_2}, ..., {s_q, t_q}] of terminal pairs and an integer k, returns an induced subgraph G^* of G that maintains all the inclusion minimal multicuts of G of size at most k, and does not contain any (k+2)-vertex connected set of size 2^O(k). In particular, G^* excludes a clique of size 2^O(k) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable algorithms for Stable s-t Separator, Stable Odd Cycle Transversal and Stable Multicut on general graphs, and for Stable Directed Feedback Vertex Set on d-degenerate graphs, resolving two problems left open by Marx et al. [ACM Transactions on Algorithms, 2013]. All of our algorithms can be derandomized at the cost of a small overhead in the running time. Based on joint work with Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi.

2:15pm to 3:00pm (209M3 Stort Auditorium)

Meirav Zehavi: Cycle Packing on General and Geometric Graphs

In this talk, we will see how to solve the Cycle Packing problem on general and geometric graphs. For general graphs, our goal will be to design an algorithm ``faster than Erdos-Posa'', while for geometric graphs, our goal will be to design a subexponential-time algorithm.

3:00pm to 3:30pm

Coffee break

3:30pm to 4:15pm (209M3 Stort Auditorium)

Bart Jansen: Gems in (the vocabulary of) multivariate algorithmics: A tribute to Mike Fellows

Mike Fellows has contributed many ideas, techniques, and problems to the field of multivariate algorithmics. But his influence is also strongly felt through the vocabulary we use! I reflect on my history with Mike based on some of the colorful terminology he introduced, while describing old and new results along the way.

4:15pm to 5:00pm (209M3 Stort Auditorium)

Amer Mouawad: Reconfiguration via graph searching

Consider the following problem. We are given an n-vertex graph G, an integer k, and two vertex covers of G, S and T, of size at most k. The goal is to determine whether S can be transformed into T by a sequence of vertex additions and removals such that every intermediate set remains a vertex cover of size at most k. This problem, known as Vertex Cover Reconfiguration, has been shown to be PSPACE-complete on graphs of bounded treewidth and polynomial-time solvable for, e.g., trees, cactus graphs, and even-hole-free graphs. It has been open whether the problem remains hard on bipartite graphs. We show that Vertex Cover Reconfiguration is NP-complete on bipartite graphs. In particular, we establish NP-hardness via a new connection between the aforementioned problem and graph searching. To show membership in NP, we prove that, for bipartite graphs, the length of such a transformation is at most O(n^4). Based on joint work with Daniel Lokshtanov.

7:30pm

Diner at Mingel Gastrobar - Bjørnsons gaten 5 (and after-party)