Bart M. P. Jansen

Talks

Expand all abstracts

65. 2nd Parameterized Algorithms & Computational Experiments Challenge

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
September 6th 2017, Vienna, Austria

This talk was given at the award ceremony of the 2nd Parameterized Algorithms & Computational Experiments Challenge (PACE 2017). The talk consists of several parts: where PACE came from (presented by me), how track A went (presented by Holger Dell), a short talk by the winning team of the exact subcompetition of track A (Felix Salfelder), how track B went (presented by Christian Komusiewicz), and a short talk by the winning team of track B (Yasuaki Kobayashi). More information about PACE can be found on the website pacechallenge.wordpress.com. The second edition of PACE was sponsored by the Networks project.

64. Kernelization Basics:
Exploring the Lost Continent of Polynomial Time [Invited lecture]

Parameterized Complexity Summer School
September 2nd 2017, Vienna, Austria

Join me on a tour through the lost continent of polynomial-time computation, where we find provably efficient and provably effective preprocessing algorithms to attack NP-hard problems. The talk introduces the concept of kernelization and showcases several fundamental ideas such as crown decompositions and the sunflower lemma. These are applied to obtain kernels for Edge Clique Cover, Vertex Cover, and Hitting Set.

63. Gems in (the vocabulary of) Multivariate Algorithmics:
A tribute to Mike Fellows

Mike Fellows' 65th birthday celebration
June 16th 2017, Bergen, Norway

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.

62. Fine-Grained Complexity Analysis of Two Classic TSP Variants [Invited talk]

2nd Highlights on Algorithms (HALG 2017)
June 11th 2017, Berlin, Germany

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. The first variant we consider is the Bitonic TSP problem: given a set of n points in the plane, compute a shortest tour consisting of two x-monotone chains. It is a classic exercise to solve this problem in O(n^2) time. We show that this is far from optimal: bitonic tours can be found in O(n log^2 n) time. The second variant is the k-OPT decision problem, which asks whether a given tour can be improved by replacing k edges. The problem can be solved in O(n^k) time for each k. We give evidence that this is optimal for k=3 using the APSP-conjecture. For larger k, we give a new algorithm that finds the best k-move in O(n^{floor{2k/3} + 1). Joint work with Mark de Berg, Kevin Buchin, and Gerhard Woeginger.

61. Micro-course on Structural Graph Parameters, part 3:
Applications

4th Training Week of the Networks Consortium
February 2nd 2017, Doorn, The Netherlands

This microcourse deals with structural graph parameters and the relations between them. A graph parameter assigns a number to a graph, by answering a question such as 'how many edges are there?', 'how many vertices are needed to intersect all the cycles?', or 'what is the size of the largest clique?'. Over the last decades, the study of structural graph theory has produced a rich toolbox of different graph parameters that also capture more subtle aspects of the structure of a graph. For example, the parameter treewidth gives a formal way to answer the question: 'how treelike is this graph?'. The goal of the microcourse is to introduce useful graph parameters and relate them to each other. The hierarchy among graph parameters facilitates a research methodology that has proven very useful: start by exploring the research question of interest on graphs that are structurally simple according to a 'very restrictive' parameter, and repeatedly generalize the resulting insights to more and more general parameters. The concepts of structural graph theory also find applications in parameterized computational complexity. When faced with a computational problem that is intractable (NP-complete) in general, one can study whether it can be solved efficiently on large graphs that are structurally simple in terms of a chosen parameter. Investigating how the computational complexity of the problem depends on the value of a structural parameter results in an extended dialogue with a computational problem that yields important insights in the types of inputs for which it can be solved efficiently. If time permits, we will explore some examples of the application of structural graph theory to parameterized complexity.

60. Micro-course on Structural Graph Parameters, part 2:
A hierarchy of graph parameters

4th Training Week of the Networks Consortium
February 1st 2017, Doorn, The Netherlands

This microcourse deals with structural graph parameters and the relations between them. A graph parameter assigns a number to a graph, by answering a question such as 'how many edges are there?', 'how many vertices are needed to intersect all the cycles?', or 'what is the size of the largest clique?'. Over the last decades, the study of structural graph theory has produced a rich toolbox of different graph parameters that also capture more subtle aspects of the structure of a graph. For example, the parameter treewidth gives a formal way to answer the question: 'how treelike is this graph?'. The goal of the microcourse is to introduce useful graph parameters and relate them to each other. The hierarchy among graph parameters facilitates a research methodology that has proven very useful: start by exploring the research question of interest on graphs that are structurally simple according to a 'very restrictive' parameter, and repeatedly generalize the resulting insights to more and more general parameters. The concepts of structural graph theory also find applications in parameterized computational complexity. When faced with a computational problem that is intractable (NP-complete) in general, one can study whether it can be solved efficiently on large graphs that are structurally simple in terms of a chosen parameter. Investigating how the computational complexity of the problem depends on the value of a structural parameter results in an extended dialogue with a computational problem that yields important insights in the types of inputs for which it can be solved efficiently. If time permits, we will explore some examples of the application of structural graph theory to parameterized complexity.

59. Micro-course on Structural Graph Parameters, part 1:
Treewidth

4th Training Week of the Networks Consortium
January 31st 2017, Doorn, The Netherlands

This microcourse deals with structural graph parameters and the relations between them. A graph parameter assigns a number to a graph, by answering a question such as 'how many edges are there?', 'how many vertices are needed to intersect all the cycles?', or 'what is the size of the largest clique?'. Over the last decades, the study of structural graph theory has produced a rich toolbox of different graph parameters that also capture more subtle aspects of the structure of a graph. For example, the parameter treewidth gives a formal way to answer the question: 'how treelike is this graph?'. The goal of the microcourse is to introduce useful graph parameters and relate them to each other. The hierarchy among graph parameters facilitates a research methodology that has proven very useful: start by exploring the research question of interest on graphs that are structurally simple according to a 'very restrictive' parameter, and repeatedly generalize the resulting insights to more and more general parameters. The concepts of structural graph theory also find applications in parameterized computational complexity. When faced with a computational problem that is intractable (NP-complete) in general, one can study whether it can be solved efficiently on large graphs that are structurally simple in terms of a chosen parameter. Investigating how the computational complexity of the problem depends on the value of a structural parameter results in an extended dialogue with a computational problem that yields important insights in the types of inputs for which it can be solved efficiently. If time permits, we will explore some examples of the application of structural graph theory to parameterized complexity.

58. Approximation and Kernelization for Chordal Vertex Deletion

28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
January 18th 2017, Barcelona, Spain

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa type packing/covering duality for holes in nearly-chordal graphs, we present a polynomial-time algorithm that reduces any instance (G,k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37--48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k^4 \log^2 k).

57. The Power of Preprocessing:
Gems in Kernelization

Aachen-Bonn-Cologne Workshop:
Combinatorial Optimization meets Parameterized Complexity [Invited talk]
December 13th 2016, Bonn, Germany

When solving a hard computational problem, the running time can often be reduced by using a preprocessing step that throws away irrelevant parts of the data which are guaranteed not to affect the final answer. Until recently, there was no good explanation for the effectiveness of preprocessing. This changed when the notion of kernelization was developed within the field of parameterized complexity. It has been called ''the lost continent of polynomial time'', since the exploration of the formal model of preprocessing captured by kernelization has led to a surprisingly rich set of techniques that can reduce the size of NP-hard problem inputs in polynomial time, without changing the answer. Using a user-defined complexity-parameter, one can also give theoretical guarantees on the amount of data reduction that is achieved. This talk gives an introduction to kernelization by showcasing some of the gems of the area: elegant preprocessing schemes built on nontrivial mathematical insights. One of the gems consists of a polynomial kernelization for the undirected Feedback Vertex Set problem. While the existence of a kernel is not new, the presented approach and its elegant correctness proof were not known before.

56. A treasure found on the lost continent of polynomial time:
Kernelization for Feedback Vertex Set

TU/e Algorithms Seminar
December 6th 2016, Eindhoven, The Netherlands

When solving a hard computational problem, the running time can often be reduced by using a preprocessing step that throws away irrelevant parts of the data which are guaranteed not to affect the final answer. Until recently, there was no good explanation for the effectiveness of preprocessing. This changed when the notion of kernelization was developed within the field of parameterized complexity. It has been called ''the lost continent of polynomial time'', since the exploration of the formal model of preprocessing captured by kernelization has led to a surprisingly rich set of techniques that can reduce the size of NP-hard problem inputs in polynomial time, without changing the answer. Using a user-defined complexity-parameter, one can also give theoretical guarantees on the amount of data reduction that is achieved. This talk presents a modern exposition of one of the treasures that has been found on the lost continent: an efficient and provably effective preprocessing algorithm for the undirected Feedback Vertex Set problem (FVS), which asks to find a minimum vertex set whose removal makes the graph acyclic. While kernelization algorithms for FVS are not new, the presented approach and its elegant correctness proof were not known before.

55. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

University of Bergen Algorithm Colloquium
October 14th 2016, Bergen, Norway

This talk investigates to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with O(n^{d-epsilon}) bits for any epsilon > 0. For the Not-All-Equal SAT problem, a compression to size tilde-O(n^{d-1}) exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with O(n^{2-epsilon}) bits for any epsilon > 0, unless NP is contained in coNP/poly.

54. 1st Parameterized Algorithms & Computational Experiments Challenge

11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
August 24th 2016, Aarhus, Denmark

This talk was given at the award ceremony of the 1st Parameterized Algorithms & Computational Experiments Challenge (PACE 2016). The talk consists of four parts: where PACE came from (presented by me), how track A went (presented by Holger Dell), how track B went (presented by Christian Komusiewicz), and what will happen for PACE in the future (again presented by me). More information about PACE can be found on the website pacechallenge.wordpress.com. The first edition of PACE was sponsored by the Networks project.

53. Fine-Grained Complexity Analysis of Two Classic TSP Variants

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
July 12th 2016, Rome, Italy

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. The first variant we consider is the Bitonic TSP problem: given a set of n points in the plane, compute a shortest tour consisting of two x-monotone chains. It is a classic exercise to solve this problem in O(n^2) time. We show that this is far from optimal: bitonic tours can be found in O(n log^2 n) time. The second variant is the k-OPT decision problem, which asks whether a given tour can be improved by replacing k edges. The problem can be solved in O(n^k) time for each k. We give evidence that this is optimal for k=3 using the APSP-conjecture. For larger k, we give a new algorithm that finds the best k-move in O(n^{floor{2k/3} + 1). Joint work with Mark de Berg, Kevin Buchin, and Gerhard Woeginger.

52. Turing Kernelization for Finding Long Paths and Cycles in Planar Graphs

Dagstuhl Seminar 16221: Algorithms for Optimization Problems in Planar Graphs
June 3rd 2016, Dagstuhl, Germany

The k-Path problem asks whether a given undirected graph has a (simple) path of length k. We prove that k-Path has polynomial-size Turing kernels when restricted to planar graphs, graphs of bounded degree, claw-free graphs, or to K_{3,t}-minor-free graphs. This means that there is an algorithm that, given a k-Path instance (G,k) belonging to one of these graph classes, computes its answer in polynomial time when given access to an oracle that solves k-Path instances of size polynomial in k in a single step. Our techniques also apply to k-Cycle, which asks for a cycle of length at least k.

51. Introduction to Fixed-Parameter Tractability
with links to Computational Geometry

Lorentz Center Workshop on Fixed-Parameter Computational Geometry [Tutorial]
April 4th 2016, Leiden, Netherlands

This tutorial introduces the main concepts in fixed-parameter tractability to an audience with a background in computational geometry. It treats both the positive toolkit (techniques for algorithms) and the negative toolkit (techniques for hardness proofs). Examples from the positive toolkit include bounded-depth search trees, kernelization, and color coding. When it comes to hardness proofs it covers W[1]-hardness and the (strong) exponential time hypothesis.

50. Fine-grained Complexity Analysis of Computational Problems on Networks

Benelux Mathematica Conference 2016 [Invited talk]
March 23rd 2016, Amsterdam, Netherlands

This talk gives an introduction to fine-grained complexity analysis, which classifies the computational complexity of problems on a finer scale than the traditional distinction between polynomial-time solvable and NP-complete problems. In recent years there have been tremendous advances in our understanding of the best-possible running time to solve classic problems on networks such as finding (all-pairs) shortest paths and detecting triangles. These new developments are based on new hypotheses about the running time of fundamental optimization problems, together with a web of intricate reductions relating the complexities of various problems to each other. The goal of the presentation is to give an accessible overview of some key results in this area concerning networks, and to give examples of the reductions that are used. For example, we will see that from the right perspective the problem of computing all pairs of shortest path distances in a graph is equivalent to the problem of finding a triangle whose sum of edge weights is negative.

49. Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight

33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016)
February 18th 2016, Orléans, France

The Constrained Bipartite Vertex Cover problem asks, for a bipartite graph G with partite sets A and B, and integers k_A and k_B, whether there is a vertex cover for G containing at most k_A vertices from A and k_B vertices from B. The problem has an easy kernel with 2 k_A * k_B edges and 4 k_A * k_B vertices, based on the fact that every vertex in A of degree more than k_B has to be included in the solution, together with every vertex in B of degree more than k_A. We prove that this kernel is asymptotically essentially optimal, both in terms of the number of vertices and the number of edges. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B,k_A,k_B) of Constrained Bipartite Vertex Cover to an equivalent instance (G',A',B',k'_A,k'_A) such that k'_A <= (k_A)^O(1), k'_B <= (k_B)^O(1), and |V(G')| <= O((k_A * k_B)^{1 - \eps}), for any \eps > 0, then NP is in coNP/poly and the polynomial-time hierarchy collapses. Using a different construction, we prove that if there is a polynomial-time algorithm that reduces any instance to an equivalent instance with O((k_A * k_B)^{1 - \eps}) edges, then NP is in coNP/poly.

48. Fine-grained Complexity and Algorithm Design

TU/e Algorithms Seminar
November 10th 2015, Eindhoven, The Netherlands

During the fall semester of 2015, the Simons institute in Berkeley hosted a research program on "fine-grained complexity and algorithm design". In this informal talk I will describe what the program was about and mention some remarkable recent results in this area. In particular, I will show how elementary reductions can establish the equivalence of a class of fundamental combinatorial problems with respect to having "truly subcubic" algorithms, even though these problems seem to behave very differently at first sight.

47. Fine-Grained Complexity Analysis of Two Classic TSP Variants

Simons Institute Fine-Grained Complexity Seminar
October 27th 2015, Berkeley, USA

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. The first variant we consider is the Bitonic TSP problem: given a set of n points in the plane, compute a shortest tour consisting of two x-monotone chains. It is a classic exercise to solve this problem in O(n^2) time. We show that this is far from optimal: bitonic tours can be found in O(n log^2 n) time. The second variant is the k-OPT decision problem, which asks whether a given tour can be improved by replacing k edges. The problem can be solved in O(n^k) time for each k. We give evidence that this is optimal for k=3 using the APSP-conjecture. For larger k, we give a new algorithm that finds the best k-move in O(n^{floor{2k/3} + 1). Joint work with Mark de Berg, Kevin Buchin, and Gerhard Woeginger.

46. Fine-Grained Complexity Analysis of Two Classic TSP Variants

TU/e Algorithms Colloquium
July 28th 2015, Eindhoven, The Netherlands

This informal board talk presented joint work with Mark de Berg, Kevin Buchin, and Gerhard Woeginger, on new results concerning two classic TSP variants. We prove that the O(n^2)-time dynamic program for finding Bitonic TSP tours among points in the plane, can be improved to O(n log^2 n). We also analyze the complexity of finding a k-OPT improvement to a given TSP tour, which is a subproblem occurring when using local search approaches for TSP. We show that the best 2-OPT and 3-OPT improvements can be found in O(n^2) and O(n^3) time, respectively, and give evidence that this is optimal. For larger k, we show that the best k-OPT move can be found in O(n^floor(2k/3)+1) time.

45. Uniform Kernelization Complexity of Hitting Forbidden Minors

42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015)
July 8th 2015, Kyoto, Japan

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. This paper analyzes to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. Fomin et al. (FOCS 2012) showed that the special case Planar F-Deletion (when F contains at least one planar graph) has a kernel of size f(F) * k^{g(F)} for some functions f and g. The degree g of the polynomial grows very quickly; it is not even known to be computable. Fomin et al. left open whether Planar F-Deletion has kernels whose size is uniformly polynomial, i.e., of the form f(F) * k^c for some universal constant c that does not depend on F. Our results in this paper are twofold. (1) We prove that some Planar F-Deletion problems do not have uniformly polynomial kernels (unless NP is in coNP/poly). In particular, we prove that Treewidth-Eta Deletion does not have a kernel with O(k^{eta/4} - eps) vertices for any eps > 0, unless NP is in coNP/poly. In fact, we even prove the kernelization lower bound for the larger parameter vertex cover number. This resolves an open problem of Cygan et al. (IPEC 2011). It is a natural question whether further restrictions on F lead to uniformly polynomial kernels. However, we prove that even when F contains a path, the degree of the polynomial must, in general, depend on the set F. (2) A canonical F-Minor-Free Deletion problem when F contains a path is Treedepth-eta Deletion: can k vertices be removed to obtain a graph of treedepth at most eta? We prove that Treedepth-eta Deletion admits uniformly polynomial kernels with O(k^6) vertices for every fixed eta. In order to develop the kernelization we prove several new results about the structure of optimal treedepth-decompositions. These insights allow us to formulate a simple, fully explicit, algorithm to reduce the instance.

44. On Structural Parameterizations of Hitting Set:
Hitting Paths in Graphs Using 2-SAT

41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)
June 19th 2015, Münich, Germany

Hitting Set is a classic problem in combinatorial optimization. Its input consists of a set system F over a finite universe U and an integer t; the question is whether there is a set of t elements that intersects every set in F. The Hitting Set problem parameterized by the size of the solution is a well-known W[2]-complete problem in parameterized complexity theory. In this paper we investigate the complexity of Hitting Set under various structural parameterizations of the input. Our starting point is the folklore result that Hitting Set is polynomial-time solvable if there is a tree T on vertex set U such that the sets in F induce connected subtrees of T. We consider the case that there is a treelike graph with vertex set U such that the sets in F induce connected subgraphs; the parameter of the problem is a measure of how treelike the graph is. Our main positive result is an algorithm that, given a graph G with cyclomatic number k, a collection P of simple paths in G, and an integer t, determines in time 2^{5k} (|G| +|P|)^O(1) whether there is a vertex set of size t that hits all paths in P. It is based on a connection to the 2-SAT problem in multiple valued logic. For other parameterizations we derive W[1]-hardness and para-NP-completeness results.

43. Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight

Workshop on Kernelization (WORKER 2015)
June 4th 2015, Nordfjordeid, Norway

The Constrained Bipartite Vertex Cover problem asks, for a bipartite graph G with partite sets A and B, and integers k_A and k_B, whether there is a vertex cover for G containing at most k_A vertices from A and k_B vertices from B. The problem has an easy kernel with 2 k_A * k_B edges and 4 k_A * k_B vertices, based on the fact that every vertex in A of degree more than k_B has to be included in the solution, together with every vertex in B of degree more than k_A. We prove that this kernel is asymptotically essentially optimal, both in terms of the number of vertices and the number of edges. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B,k_A,k_B) of Constrained Bipartite Vertex Cover to an equivalent instance (G',A',B',k'_A,k'_A) such that k'_A <= (k_A)^O(1), k'_B <= (k_B)^O(1), and |V(G')| <= (k_A * k_B)^(1 - eps), for any eps > 0, then NP is in coNP/poly and the polynomial-time hierarchy collapses. Using a different construction, we prove that if there is a polynomial-time algorithm that reduces any instance to an equivalent instance with O((k_A * k_B)^(1 - eps) edges, then NP is in coNP/poly.

42. Turing Kernelization for Finding Long Paths
and Cycles in Restricted Graph Classes

Workhop on Kernelization (WORKER 2015)
June 3rd 2015, Nordfjordeid, Norway

We present a set of results concerning the existence of polynomial-size Turing kernels for the problems of finding long simple paths and cycles in restricted graph families such as planar graphs, bounded-degree graphs, and claw-free graphs. The adaptive Turing kernelization works on the Tutte decomposition of the graph into triconnected components. Existing graph-theoretical lower bounds on the length of long paths in triconnected graphs allow us to answer YES if the Tutte decomposition has a bag of size superpolynomial in k. If this is not the case, we can identify a vertex that is irrelevant to the solution in polynomial time by querying an oracle for long paths or cycles in leaf components of the decomposition. The number of vertices involved in these queries is therefore polynomial in k, resulting in polynomial-size Turing kernels. The employed method is called Decompose-Query-Reduce and is potentially useful for other problems. Our Turing kernel shows that on these restricted graph classes, the hard part of the computation for finding a length-k path or cycle can be restricted to graphs whose size is polynomial in k.

41. On Sparsification for Computing Treewidth

Meeting on Tree-width And Combinatorial Optimization (TACO)
March 16th 2015, Eindhoven, The Netherlands

We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses.

Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by vertex cover, we improve the O(k^3)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^2) vertices. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al.(STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.

40. Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels

University of Edinburgh Algorithm Seminar
January 16th 2015, Edinburgh, United Kingdom

We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to a subgraph of G, or determine the maximum number of vertex-disjoint H-subgraphs that can be packed in G. We investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomial-time solvable, (b) admits a polynomial (many-one) kernel, or (c) admits a polynomial Turing kernel. Joint work with Dániel Marx.

39. Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels

26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
January 4th 2015, San Diego, California, USA

We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to a subgraph of G, or determine the maximum number of vertex-disjoint H-subgraphs that can be packed in G. We investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomial-time solvable, (b) admits a polynomial (many-one) kernel, or (c) admits a polynomial Turing kernel. Joint work with Dániel Marx.

38. Uniform Kernelization Complexity of Hitting Forbidden Minors

Dagstuhl Seminar 14451: Optimality and tight results in parameterized complexity
November 5th 2014, Dagstuhl, Germany
Blackboard talk

Several results are known concerning the optimality of the sizes of problem kernels. For example, a result of Dell and van Melkebeek shows that k-Vertex Cover does not have a kernel with O(k^(2-epsilon)) bits, for any positive epsilon, unless NP is in coNP/poly. For other problems, we are much further from establishing the optimal kernel size. A large family of vertex deletion problems can be captured in the framework of F-Minor-free Deletion problems. For a fixed, finite family F, the F-Minor-free Deletion problem takes as input a graph G and an integer k, and asks whether k vertices can be removed from G such that the resulting graph does not contain any graph in F as a minor. This generalizes k-Vertex Cover, k-Feedback Vertex Set, k-Vertex Planarization, and other problems. A breakthrough result by Fomin et al. (FOCS 2012) shows that if F contains a planar graph (implying that F-minor-free graphs have constant treewidth), the F-Minor-Free deletion problem has a polynomial kernel. Concretely, there is a function g (which is not known to be computable) such that F-Minor-Free deletion has a kernel with O(k^(g(F))) vertices. As F-Minor-Free deletion captures a large number of classic problems, it would be desirable to find kernels of optimal size. A first question towards finding the optimal kernel size for such problems is whether F-Minor-Free deletion has kernels of uniformly polynomial size, i.e., of size g(F) * k^c for some constant c that does not depend on the family F. We show that this is not the case: assuming NP is not in coNP/poly, F-Minor-Free deletion does not have uniformly polynomial kernels. We can also prove the following contrasting, positive result: there is a function g such that, for every t, the Treedepth-t Deletion problem has a kernel with g(k) * k^c vertices for a small, absolute constant c. Since for every fixed t, the Treedepth-t deletion problem is an instance of F-Minor-Free deletion, this shows that when the family of forbidden minors enforce sufficient structure on the solution graphs, uniformly polynomial kernels can be obtained. Our results therefore form the first step into analyzing exactly which aspects of the family of forbidden minors determine the degree of the polynomial in the optimal kernel size. Joint work with Archontia Giannopoulou, Daniel Lokshtanov, and Saket Saurabh.

37. Parameterized Algorithmics

Networks Project Meeting
October 17th 2014, Amsterdam, The Netherlands

In this talk for the Networks project I try to bridge the gap between researchers working on algorithmics and researchers working on stochastics. I introduce the framework of parameterized algorithmics for the analysis of NP-hard problems, and suggest some problems on the interface of algorithmics and stochastics.

36. Pleased to meet you

Department Dialogue, Eindhoven University of Technology
October 16th 2014, Eindhoven, The Netherlands

In a 15-minute informal talk I introduce both my personal and research background for the department in Eindhoven.

35. Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels

Max Planck Institut für Informatik
October 7th 2014, Saarbrücken, Germany
Blackboard talk

We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to a subgraph of G, or determine the maximum number of vertex-disjoint H-subgraphs that can be packed in G. We investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomial-time solvable, (b) admits a polynomial (many-one) kernel (that is, has a polynomial-time preprocessing procedure that creates an equivalent instance whose size is polynomially bounded by the size of the solution), or (c) admits a polynomial Turing kernel (that is, has an adaptive polynomial-time procedure that reduces the problem to a polynomial number of instances, each of which has size bounded polynomially by the size of the solution). In an informal board talk I will present the context for our investigations, the concrete results we obtained, and sketch some of the technical ideas that are involved. This is joint work with Daniel Marx and will be presented at SODA 2015 in January.

34. The Power of Preprocessing

Eindhoven University of Technology
September 29th 2014, Eindhoven, The Netherlands

I recently joined the Algorithms & Visualization group at the TU Eindhoven. Most of my work so far concerns provably effective and efficient preprocessing for NP-hard problems, which can be formalized using the language of parameterized complexity theory. In my first lecture here in Eindhoven I will give a gentle introduction into this field, highlighted by pointers to some of my recent work. I will introduce and motivate the basic notion of kernelization that captures good preprocessing. Afterward we will also consider some variations of this basic model. We conclude by considering a recent preprocessing algorithm for the Longest Path problem in more detail. I presented this algorithm at the European Symposium on Algorithms two weeks ago.

33. Turing Kernelization for Finding Long Paths
and Cycles in Restricted Graph Classes

22nd European Symposium on Algorithms (ESA 2014)
September 8th 2014, Wrocław, Poland

We present a set of new results concerning the existence of polynomial-size Turing kernels for the problems of finding long simple paths and cycles in restricted graph families such as planar graphs, bounded-degree graphs, and claw-free graphs. The adaptive Turing kernelization works on the Tutte decomposition of the graph into triconnected components. Existing graph-theoretical lower bounds on the length of long paths in triconnected graphs allow us to answer YES if the Tutte decomposition has a bag of size superpolynomial in k. If this is not the case, we can identify a vertex that is irrelevant to the solution in polynomial time by querying an oracle for long paths or cycles in leaf components of the decomposition. The number of vertices involved in these queries is therefore polynomial in k, resulting in polynomial-size Turing kernels. The employed method is called Decompose-Query-Reduce and is potentially useful for other problems. Our Turing kernel shows that on these restricted graph classes, the hard part of the computation for finding a length-k path or cycle can be restricted to graphs whose size is polynomial in k.

32. Parameterized Algorithms: Advanced Kernelization Techniques

School on Parameterized Algorithms and Complexity
August 20th 2014, Będlewo, Poland

This is a lecture of the 2014 School on Parameterized Algorithms and Complexity that was held in Będlewo, Poland. The topic is advanced kernelation techniques. The lecture is roughly split in two parts. The first part shows how many problems become easier when restricted to planar graphs. A 4k-vertex kernel is developed for Connected Vertex Cover in planar graphs, while the problem does not admit a polynomial kernel in general graphs unless the polynomial-time hierarchy collapses. The second part of the lecture focuses on Turing kernelization. The simple example of the Max Leaf Subtree shows that Turing kernelization can be used to analyze meaningful preprocessing schemes for problems that do not have traditional kernels of small size. We conclude by considering the very recent Turing kernel for the Longest Path problem on planar graphs.

31. Parameterized Algorithms: Randomized Algorithms

School on Parameterized Algorithms and Complexity
August 18th 2014, Będlewo, Poland

This was the third lecture of the 2014 School on Parameterized Algorithms and Complexity that was held in Będlewo, Poland. It deals with randomized FPT algorithms, mostly using the color coding paradigm. Randomized FPT algorithms are presented for Longest Path, Subgraph Isomorphism on Bounded-Degree graphs, and d-Clustering. After briefly considering the derandomization issue, the lecture concludes with a simple randomized algorithm for Feedback Vertex Set.

30. Parameterized Algorithms: The Basics

School on Parameterized Algorithms and Complexity
August 18th 2014, Będlewo, Poland

This was the opening lecture of the 2014 School on Parameterized Algorithms and Complexity that was held in Będlewo, Poland. After briefly surveying the history of parameterized complexity, it starts by defining the basics concepts of parameterized tractability. Three types of parameterized algorithms are presented: kernelization algorithms (illustrated for Vertex Cover and Feedback Arc Set in Tournaments), bounded-depth search trees (illustrated for Vertex Cover and Feedback Vertex Set), and dynamic programming over subsets (illustrated for Set Cover).

29. The Power of Preprocessing

Eindhoven University of Technology
July 13th 2014, Eindhoven, The Netherlands

During this 20-minute talk I give an informal overview of some of my recent work concerning preprocessing, (Turing) kernelization, and parameterized algorithmics. The high-level ideas are conveyed through pictures, along with pointers to my research papers. Among the discussed papers are a recent result with Daniel Marx concerning preprocessing for finding patterns in large networks, the survey paper with Mike Fellows and Frances Rosamond suggesting a wide exploration of the parameter landscape, a paper on graph coloring with Stefan Kratsch, my recent paper on Turing kernelization for finding long paths in planar graphs, and a paper with Daniel Lokshtanov and Saket Saurabh concerning efficient parameterized algorithms for the planarization problem.

28. Turing Kernelization for Finding Long Paths
and Cycles in Restricted Graph Classes

University of Bergen Algorithm Colloquium
May 9th 2014, Bergen, Norway
Blackboard talk

In this informal board talk we present a set of new results concerning the existence of polynomial-size Turing kernels for the problems of finding long simple paths and cycles in restricted graph families such as planar graphs, bounded-degree graphs, and claw-free graphs. The adaptive Turing kernelization works on the Tutte decomposition of the graph into triconnected components. Existing graph-theoretical lower bounds on the length of long paths in triconnected graphs allow us to answer YES if the Tutte decomposition has a bag of size superpolynomial in k. If this is not the case, we can identify a vertex that is irrelevant to the solution in polynomial time by querying an oracle for long paths or cycles in leaf components of the decomposition. The number of vertices involved in these queries is therefore polynomial in k, resulting in polynomial-size Turing kernels. The employed method is called Decompose-Query-Reduce and is potentially useful for other problems. Our Turing kernel shows that on these restricted graph classes, the hard part of the computation for finding a length-k path or cycle can be restricted to graphs whose size is polynomial in k.

27. Turing Kernelization for Finding Long Paths
and Cycles in Restricted Graph Classes

Institute of Mathematical Sciences
April 17th 2014, Chennai, India
Blackboard talk

In this informal board talk we present a set of new results concerning the existence of polynomial-size Turing kernels for the problems of finding long simple paths and cycles in restricted graph families such as planar graphs, bounded-degree graphs, and claw-free graphs. The adaptive Turing kernelization works on the Tutte decomposition of the graph into triconnected components. By processing the Tutte decomposition from bottom to top and making repeated use of the existence of an oracle that decides small instances of an NP-complete problem, we are able to reduce the size of the graph to polynomial in k without changing the answer. The employed method is called Decompose-Query-Reduce and is potentially useful for other problems. Our Turing kernel shows that on these restricted graph classes, the hard part of the computation for finding a length-k path or cycle can be restricted to graphs whose size is polynomial in k.

26. New developments in Circuit Complexity:
From Circuit-SAT Algorithms to Circuit Lower Bounds

UiB Winter School on Algorithms
March 20th 2014, Finse, Norway

In 2010, Ryan Williams suggested a new route to proving circuit lower bounds. He showed that the existence of algorithms for testing the satisfiability of a Boolean circuit that run slightly faster than brute force, imply superpolynomial circuit lower bounds for languages in the class NEXP. One year later he proved that for the restricted class of constant-depth circuits with mod gates (ACC) such circuit satisfiability algorithms exist. By adapting his earlier arguments this led to a proof that NEXP does not have non-uniform ACC circuits of polynomial size. In this tutorial we present the main ideas behind the proof while highlighting the role of algorithms in this circuit complexity breakthrough.

25. A Near-Optimal Planarization Algorithm

Dagstuhl Seminar 14071: Graph Modification Problems
February 13th 2014, Dagstuhl, Germany

The problem of testing whether a graph is planar has been studied for over half a century, and is known to be solvable in O(n) time using a myriad of different approaches and techniques. Robertson and Seymour established the existence of a cubic algorithm for the more general problem of deciding whether an n-vertex graph can be made planar by at most k vertex deletions, for every fixed k. Of the known algorithms for k-Vertex Planarization, the algorithm of Marx and Schlotter (WG 2007, Algorithmica 2012) running in time 2^{k^{O(k^3)}} n^2 achieves the best running time dependence on k. The algorithm of Kawarabayashi (FOCS 2009), running in time f(k)n for some f(k) >= 2^{k^{k^3}} that is not stated explicitly, achieves the best dependence on n.

We present an algorithm for k-Vertex Planarization with running time 2^O(k log k) n, significantly improving the running time dependence on k without compromising the linear dependence on n. Our main technical contribution is a novel scheme to reduce the treewidth of the input graph to O(k) in time 2^O(k log k) n. It combines new insights into the structure of graphs that become planar after contracting a matching, with a Baker-type subroutine that reduces the number of disjoint paths through planar parts of the graph that are not affected by the sought solution. To solve the reduced instances we formulate a dynamic programming algorithm for Weighted Vertex Planarization on graphs of treewidth w with running time 2^O(w log w) n, thereby improving over previous double-exponential algorithms.

While Kawarabayashi's planarization algorithm relies heavily on deep results from the graph minors project, our techniques are elementary and practically self-contained. We expect them to be applicable to related edge-deletion and contraction variants of planarization problems.

24. A Near-Optimal Planarization Algorithm

25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
January 7th 2014, Portland, Oregon, USA

The k-Vertex Planarization problem asks whether a graph G can be made planar by deleting k vertices. We show that the problem can be solved in time 2^O(k log k) n, thereby improving on an earlier algorithm by Kawarabayashi (FOCS 2009) with running time O(2^k^O(k^3)) * n. While earlier planarization algorithms relied heavily on deep results from the graph minors project, our techniques are elementary and practically self-contained.

23. On Sparsification for Computing Treewidth

TU Berlin, "Algorithmik und Komplexitätstheorie" Colloquium
November 27th 2013, Berlin, Germany

Many optimization problems can be solved efficiently on graphs of bounded treewidth, if a tree decomposition is known. Unfortunately, computing a minimum-width tree decomposition of a graph is NP-hard and can therefore form a bottleneck in such approaches. In the past, it has been observed that the use of heuristic reduction rules speeds up the process of finding tree decompositions significantly. We analyze two aspects of preprocessing for computing treewidth decompositions theoretically, using the framework of parameterized complexity.

Our first result concerns the possibility of polynomial-time sparsification. We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. In particular, the lower bound shows that Treewidth parameterized by the size of a vertex cover does not have a kernel with O(k^{2-e}) bits (unless ..).

Our second result tightens the gap between the upper- and lower bounds for Treewidth parameterized vertex cover. We improve the O(k^3)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^2) vertices, which can be encoded in O(k^3) bits. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al.(STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.

22. On Sparsification for Computing Treewidth

University of Bergen Algorithm Colloquium
September 20th 2013, Bergen, Norway

We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses.

Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by vertex cover, we improve the O(k^3)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^2) vertices. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al.(STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.

21. On Sparsification for Computing Treewidth

8th International Symposium on Parameterized and Exact Computation (IPEC 2013)
September 4th 2013, Sophia Antipolis, France

We study whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is not the case: if there is an e>0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses.

Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e>0, unless NP is in coNP/poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by vertex cover, we improve the O(k^3)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^2) vertices. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al.(STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.

20. FPT is Characterized by Useful Obstruction Sets

39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)
June 21st 2013, Lübeck, Germany

Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable, obstruction sets and efficient order tests is not just one way of obtaining strongly uniform FPT algorithms, but that all of FPT may be captured in this way. Our new characterization of FPT has a strong connection to the theory of kernelization, as we prove that problems with polynomial kernels can be characterized by obstruction sets whose elements have polynomial size. Consequently we investigate the interplay between the sizes of problem kernels and the sizes of the elements of such obstruction sets, obtaining several examples of how results in one area yield new insights in the other. We show how exponential-size minor-minimal obstructions for pathwidth k form the crucial ingredient in a novel OR-cross-composition for k-Pathwidth, complementing the trivial AND-composition that is known for this problem. In the other direction, we show that OR-cross-compositions into a parameterized problem can be used to rule out the existence of efficiently generated quasi-orders on its instances that characterize the NO-instances by polynomial-size obstructions.

19. Kernel Bounds for Structural Parameterizations of Pathwidth

13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012)
July 6th 2012, Helsinki, Finland

Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters.

Our main result is that, unless NP is contained in coNP/poly, Pathwidth admits no polynomial kernelization even when parameterized by the vertex deletion distance to a clique, by giving a cross-composition from Cutwidth. The cross-composition works also for Treewidth, improving over previous lower bounds by the present authors. For Pathwidth, our result rules out polynomial kernels with respect to the distance to various classes of polynomial-time solvable inputs, like interval or cluster graphs.

This leads to the question whether there are nontrivial structural parameters for which Pathwidth does admit a polynomial kernelization. To answer this, we give a collection of graph reduction rules that are safe for Pathwidth. We analyze the success of these results and obtain polynomial kernelizations with respect to the following parameters: the size of a vertex cover of the graph, the vertex deletion distance to a graph where each connected component is a star, and the vertex deletion distance to a graph where each connected component has at most c vertices.

18. Preprocessing Graph Problems: When Does a Small Vertex Cover Help?

Dagstuhl Seminar 12241: Data Reduction and Problem Kernels
June 13th 2012, Dagstuhl, Germany

We prove a number of results around kernelization of problems parameterized by the vertex cover of a graph. We provide two simple general conditions characterizing problems admitting kernels of polynomial size. Our characterizations not only give generic explanations for the existence of many known polynomial kernels for problems like Odd Cycle Transversal, Chordal Deletion, Planarization, eta-Transversal, Long Path, Long Cycle, or H-packing, they also imply new polynomial kernels for problems like F-Minor-Free Deletion, which is to delete at most k vertices to obtain a graph with no minor from a fixed finite set F.

While our characterization captures many interesting problems, the kernelization complexity landscape of problems parameterized by vertex cover is much more involved. We demonstrate this by several results about induced subgraph and minor containment, which we find surprising. While it was known that testing for an induced complete subgraph has no polynomial kernel unless NP is in coNP/poly, we show that the problem of testing if a graph contains a given complete graph on t vertices as a minor admits a polynomial kernel. On the other hand, it was known that testing for a path on t vertices as a minor admits a polynomial kernel, but we show that testing for containment of an induced path on t vertices is unlikely to admit a polynomial kernel.

17. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

University of Bergen Algorithm Colloquium
October 28th 2011, Bergen, Norway
Blackboard talk

In an informal blackboard-talk I will describe some results of a recent paper at ICALP, where we studied whether efficient preprocessing schemes for the Treewidth problem can give provable bounds on the size of the processed instances using the framework of kernelization. Assuming the AND-distillation conjecture to hold, the standard parameterization of Treewidth does not have a kernel of polynomial size and thus instances (G, k) of the decision problem of Treewidth cannot be efficiently reduced to equivalent instances of size polynomial in k. We therefore consider different (structural) parameterizations of the Treewidth problem. We show that Treewidth has a kernel with O(l^3) vertices, with l the size of a vertex cover, and a kernel with O(l^4) vertices, with l the size of a feedback vertex set. I will try to share some insights into how the reduction rules were found, and their relationship to experimental work on preprocessing heuristics for treewidth. We also obtained various kernel lower-bounds. Treewidth parameterized by the vertex-deletion distance to a co-cluster graph and Weighted Treewidth parameterized by the size of a vertex cover do not have polynomial kernels unless NP \subseteq coNP/poly. Treewidth parameterized by the deletion distance to a cluster graph has no polynomial kernel unless the AND-distillation conjecture does not hold. If time permits I will show which properties of treewidth were exploited in the reductions that yield these lower-bounds.

16. Kernel Bounds for Path and Cycle Problems

6th International Symposium on Parameterized and Exact Computation (IPEC 2011)
September 8th 2011, Saarbrücken, Germany

Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

15. Kernelization for a Hierarchy of Structural Parameters

The Third Workshop on Kernelization (WORKER 2011) [Invited talk]
September 3rd 2011, Vienna, Austria

There are various reasons to study the kernelization complexity of non-standard parameterizations. Problems such as Chromatic Number are NP-complete for a constant value of the natural parameter, hence we should not hope to obtain kernels for this parameter. For other problems such as Long Path, the natural parameterization is fixed-parameter tractable but is known not to admit a polynomial kernel unless the polynomial hierarchy collapses. We may therefore guide the search for meaningful preprocessing rules for these problems by studying the existence of polynomial kernels for different parameterizations.

Another motivation is formed by the Vertex Cover problem. Its natural parameterization admits a small kernel, but there exist refined parameters (such as the feedback vertex number) which are structually smaller than the natural parameter, for which polynomial kernels still exist; hence we may obtain better preprocessing studying the properties of such refined parameters.

In this survey talk we discuss recent results on the kernelization complexity of structural parameterizations of these important graph problems. We consider a hierarchy of structural graph parameters, and try to pinpoint the best parameters for which polynomial kernels still exist.

14. Data Reduction for Graph Coloring Problems

Fundamentals of Computation Theory - 18th International Symposium (FCT 2011)
August 22nd 2011, Oslo, Norway

This paper studies the kernelization complexity of graph coloring problems, with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai's study of the time complexity with respect to these parameters.

13. Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
March 10th 2011, Dortmund, Germany
pptxpptpdf

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

12. Vertex Cover Kernelization for a Refined Parameter: Upper and Lower bounds

Meeting on Tree-width And Combinatorial Optimization (TACO)
January 12th 2011, Utrecht, The Netherlands

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

11. Vertex Cover Kernelization for a Refined Parameter: Upper and Lower bounds

University of Bergen Algorithm Colloquium
January 7th 2011, Bergen, Norway

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

10. Kernelization Lower Bounds: Review of existing techniques and the introduction of Cross-composition

The Second Workshop on Kernelization (WORKER 2010) [Invited talk]
November 10th 2010, Leiden, The Netherlands
pptpptx

This presentation focuses on super-polynomial lower bounds on kernel sizes. The first half of the talk treats the existing techniques for proving such lower bounds. We start by considering OR-compositions, which allow us to prove that k-Path does not admit a polynomial kernel unless the polynomial hierarchy collapses. We then show that the framework can be extended by using polynomial-parameter transformations, which leads to a kernel lower bound for Disjoint Cycles by using the intermediate problem Disjoint Factors. Without going into details we discuss several other applications of this framework to obtain lower bounds for Connected Vertex Cover, Small Universe Set Cover and Small Universe Hitting Set. In the second half of the talk we introduce the new technique of cross-composition. We discuss how cross-composition generalizes and extends the two existing techniques, and give an application of cross-composition by proving that the Clique problem parameterized by size of a vertex cover of the graph does not admit a polynomial kernel (unless ..).

9. Vertex Cover Kernelization for a Refined Parameter: Upper and Lower bounds

ALGORITMe Staff Colloquium Utrecht Utrecht University
September 10th 2010, Utrecht, The Netherlands

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

8. Polynomial Kernels for Hard Problems on Disk Graphs

12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010)
June 23rd 2010, Bergen, Norway

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k2+6k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

7. Polynomial Kernels for Hard Problems on Disk Graphs

Meeting on Tree-width And Combinatorial Optimization (TACO)
June 10th 2010, Aachen, Germany

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k2+6k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

6. Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights

7th International Conference on Algorithms and Complexity (CIAC 2010)
May 27th 2010, Rome, Italy

In this paper we consider a natural generalization of the well-known Max Leaf Spanning Tree problem. In the generalized Weighted Max Leaf problem we get as input an undirected connected graph G=(V,E), a rational number k≥1 and a weight function w mapping from vertices to rational numbers ≥ 1, and are asked whether a spanning tree T for G exists such that the combined weight of the leaves of T is at least k. We show that it is possible to transform an instance (G,w,k) of Weighted Max Leaf in linear time into an equivalent instance (G',w',k') such that |V'| ≤ 5.5k' and k'≤k. In the context of fixed parameter complexity this means that Weighted Max Leaf admits a kernel with 5.5k vertices. The analysis of the kernel size is based on a new extremal result which shows that every graph G that excludes some simple substructures always contains a spanning tree with at least |V|/5.5 leaves.

5. Polynomial Kernels for Hard Problems on Disk Graphs

ALGORITMe Staff Colloquium Utrecht Utrecht University
April 16th 2010, Utrecht, The Netherlands

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k2+6k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

4. Fixed Parameter Complexity of the Weighted Max Leaf Problem

Master Thesis Presentation Utrecht University
July 3rd 2009, Utrecht, The Netherlands

In this paper we consider the fixed parameter complexity of the Weighted Max Leaf problem, where we get as input an undirected connected graph G = (V,E) with a weight function w: V -> N on the vertices and are asked whether a spanning tree for G exists such that the combined weight of the leaves of the tree is at least k. The fixed parameter complexity of this problem strongly depends on the weight range that is allowed. If we allow vertices to have a weight of zero (the range of the weight function is the non-negative integers) then this problem is hard for W[1] on general graphs. When we restrict the problem to specific graph classes, we can obtain linear size problem kernels for these non-negative weights. We show the existence of a kernel with 78k vertices on planar graphs, O(sqrt(g)k + g) vertices on graphs of oriented genus at most g, and with (1 + 4d)(1 + d/2)k vertices on graphs in which the degree of positive-weight vertices is bounded by d. If we require all vertex weights to be strictly positive integers, we can prove the existence of a problem kernel with 7.5k vertices on general graphs. For the correctness proofs of the problem kernels we develop some extremal graph theory about spanning trees with many leaves in bipartite graphs, and in graphs that do not have long paths of degree-2 vertices.

3. Fixed parameter tractability and kernelization for the Maximum Leaf Weight Spanning Tree problem

Meeting on Tree-width And Combinatorial Optimization (TACO)
May 12th 2009, Maastricht, The Netherlands

The Maximum Leaf Spanning Tree asks for a connected graph G and integer k whether there exists a spanning tree for G with at least k leaves. Recall that a leaf in a tree is a vertex with degree 1. The subject of this talk is the generalization of this problem into the Maximum Leaf Weight Spanning Tree (MLWST) problem, in which we give each vertex a non-negative integer weight and ask if the graph has a spanning tree such that the combined weight of all the leaves is at least k. We consider the fixed parameter (in)tractability of this problem. We show that MLWST is hard for W[1] on general graphs. The problem is Fixed Parameter Tractable (FPT) when restricted to graphs of bounded genus, which will be shown by presenting a linear sized problem kernel for these classes of graphs. This means that for those classes of graphs we can always apply polynomial time data reduction to simplify the problem instance to an equivalent instance whose size does not depend on |G|, but only on k.

2. Fixed parameter tractability and kernelization for the White-Black Max-Leaf Spanning Tree problem

ALGORITMe Staff Colloquium Utrecht University
March 6th 2009, Utrecht, The Netherlands

In the classic Maximum Leaf Spanning Tree problem, the input consists of a graph and the goal is to find a spanning tree for that graph that maximizes the number of leaves. We consider a generalization of the problem where the input consists of a graph whose vertices are colored either black or white, and the goal is to maximize the number of black leaves in a spanning tree. The problem is analyzed using the toolbox of parameterized complexity. We obtain several positive and negative results in the form of W[1]-hardness proofs and kernelization upper bounds. It turns out that to obtain positive results, we must restrict ourselves to planar graphs.

1. Heuristics for Road Network Augmentation

5th Dutch Computational Geometry Day
July 3rd 2008, Eindhoven, The Netherlands

In the social studies, it is common practice to study the relationship between socio-economic factors in various populations. It is not unusual for one of these factors to be the accessibility of a certain location. For example, one might study the correlation between the number of deaths in a certain village caused by a heart attack, and the proximity of that village to the nearest hospital. In general, the accessibility of speci c facilities often play a role in such studies.

When a detailed roadmap of an area is known, this roadmap can be used to compute shortest paths in a network. The lengths of these shortest paths can be used as a measure for accessibility. But these approaches fail when the road structure of an area is not known. Since there are large parts of the world for which there are no detailed roadmaps - think of third world countries, for example - this poses a problem when performing a socio-economic study on such an area. One solution to this problem is to augment the network with extra roads that are hypothesized to exist, but of which no information is known. The goal of such a step is to ensure that the road network forms a connected graph, such that regular accessibility analysis can be performed. In this talk we present experimental results on the results of various heuristics for road network augmentation.