Author name cluster

Bart M.P. Jansen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2020 Journal Article

Polynomial kernels for hitting forbidden minors under structural parameterizations

Bart M.P. Jansen
Astrid Pieterse

We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F -Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance ( G, k ) can be reduced in polynomial time to an equivalent one of size k O ( 1 ). In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F -Deletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth η. We prove that for each set F of connected graphs and constant η, the F -Deletion problem parameterized by the size of a treedepth-η modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F -Deletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G − X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F -Deletion solution from a single connected component of G − X. By bounding the number of different types of behavior that can occur by a polynomial in | X |, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F -Deletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for F -Deletion parameterized by a vertex cover, which is a treedepth-one modulator.

Details DOI

TCS Journal 2019 Journal Article

Computing the chromatic number using graph decompositions via matrix rank

Bart M.P. Jansen
Jesper Nederlof

Computing the smallest number q such that the vertices of a given graph can be properly q-colored, known as the chromatic number, is one of the oldest and most fundamental problems in combinatorial optimization. The q -Coloring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. For example, algorithms are known to solve the problem on graphs of treewidth tw in time O ⁎ ( q tw ), while a running time of O ⁎ ( ( q − ε ) tw ) is impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q -Coloring parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators. We present two algorithms for q -Coloring parameterized by cutwidth ctw: a deterministic one that runs in time O ⁎ ( 2 ω ⋅ ctw ), where ω is the square matrix multiplication exponent, and a randomized one with runtime O ⁎ ( 2 ctw ). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-Coloring cannot be solved in O ⁎ ( ( 2 − ε ) ctw ) time assuming SETH. Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O ⁎ ( ( ⌊ d / 2 ⌋ + 1 ) pw ) time randomized algorithm for q -Coloring on graphs of pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O ⁎ ( ( ⌊ d / 2 ⌋ + 1 − ε ) pw ) -time algorithm exists assuming SETH.

Details DOI

I&C Journal 2013 Journal Article

Data reduction for graph coloring problems

Bart M.P. Jansen
Stefan Kratsch

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. Our results show that the existence of polynomial kernels for q-Coloring parameterized by the vertex-deletion distance to a graph class F is strongly related to the existence of a function f ( q ) which bounds the number of vertices which are needed to preserve the no-answer to an instance of q-List Coloring on F.

Details DOI

TCS Journal 2013 Journal Article

Kernel bounds for path and cycle problems

Hans L. Bodlaender
Bart M.P. Jansen
Stefan Kratsch

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.

Details DOI

TCS Journal 2013 Journal Article

Parameterized complexity of vertex deletion into perfect graph classes

Pinar Heggernes
Pim van ’t Hof
Bart M.P. Jansen
Stefan Kratsch
Yngve Villanger

Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F -Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the resulting graph belongs to F. Whether Perfect Deletion is fixed-parameter tractable, and whether Chordal Deletion admits a polynomial kernel, when parameterized by k, have been stated as open questions in previous work. We show that Perfect Deletion and Weakly Chordal Deletion are W [ 2 ] -hard when parameterized by k. In search of positive results, we study a restricted variant of the F -Deletion problem. In this restricted variant, the deleted vertices must be taken from a specified set X, and we parameterize by | X |. We show that for Perfect Deletion and Weakly Chordal Deletion, although this restriction immediately ensures fixed-parameter tractability, it is not enough to yield polynomial kernels, unless NP ⊆ coNP / poly. On the positive side, for Chordal Deletion, the restriction enables us to obtain a kernel with O ( | X | 4 ) vertices.

Details DOI