14 citations · 22 across the 11 of their papers we have counts for
16 papers · 1 filter
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
Bart M. P. Jansen, Michał Włodarczyk
In the F-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family F. The Vertex planarization pr…
Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size
Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk
In the -Minor-Free Deletion problem one is given an undirected graph , an integer , and the task is to determine whether there exists a vertex set of size at…
On the Hardness of Compressing Weights
Bart M. P. Jansen, Shivesh K. Roy, Michał Włodarczyk
We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the inst…
FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
Bart M. P. Jansen, Jari J. H. de Kroon
For a hereditary graph class , the -elimination distance of a graph is the minimum number of rounds needed to reduce to a member of …
Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
Bart M. P. Jansen, Jari J. H. de Kroon
We consider the -free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties . Given an input graph , this problem asks whether ther…
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen +1
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can b…