The University of Hong Kong
Hong Kong
University of Bergen
Bergen, Norway
University of Bergen
Bergen, Norway
Eindhoven University of Technology
The Netherlands
Université Blaise Pascal
Clermont-Ferrand, France
University of Bergen
Bergen, Norway
University of Bergen
Bergen, Norway
University of Bergen
Bergen, Norway
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).
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
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.
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.
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.
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.
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.
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.