
Close relatives (of Feedback Vertex Set), revisited
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a numb...
read it

Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
read it

Hardness of Metric Dimension in Graphs of Constant Treewidth
The Metric Dimension problem asks for a minimumsized resolving set in a...
read it

Quasipolynomialtime algorithm for Independent Set in P_tfree graphs via shrinking the space of induced paths
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...
read it

The Complexity of Connectivity Problems in ForbiddenTransition Graphs and EdgeColored Graphs
The notion of forbiddentransition graphs allows for a robust generaliza...
read it

Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
read it

Solving hard cut problems via flowaugmentation
We present a new technique for designing FPT algorithms for graph cut pr...
read it

Two lower bounds for pcentered colorings
Given a graph G and an integer p, a coloring f : V(G) →ℕ is pcentered i...
read it

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
read it

Covering minimal separators and potential maximal cliques in P_tfree graphs
A graph is called P_tfree if it does not contain a tvertex path as an ...
read it

Induced subgraphs of bounded treewidth and the container method
A hole in a graph is an induced cycle of length at least 4. A hole is lo...
read it

Optimal Discretization is Fixedparameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
read it

A Double Exponential Lower Bound for the Distinct Vectors Problem
In the (binary) Distinct Vectors problem we are given a binary matrix A ...
read it

Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
read it

Cluster Editing parameterized above the size of a modificationdisjoint P_3 packing is paraNPhard
Given a graph G=(V,E) and an integer k, the Cluster Editing problem asks...
read it

Quasipolynomial time approximation schemes for the Maximum Weight Independent Set Problem in Hfree graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
read it

Packing directed circuits quarterintegrally
The celebrated ErdősPósa theorem states that every undirected graph tha...
read it

Efficient approximation schemes for uniformcost clustering problems in planar graphs
We consider the kMedian problem on planar graphs: given an edgeweighte...
read it

Improved bounds for the excludedminor approximation of treedepth
Treedepth, a more restrictive graph width parameter than treewidth and p...
read it

A PolynomialTime Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non...
read it

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
A hole in a graph is an induced cycle of length at least 4, and an antih...
read it

Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: HalfIntegral Relaxations and Matroidbased Kernelization
In the recent years we have witnessed a rapid development of new algorit...
read it

Randomized contractions meet lean decompositions
The randomized contractions technique, introduced by Chitnis et al. in 2...
read it

Multibudgeted directed cuts
We study multibudgeted variants of the classic minimum cut problem and ...
read it

A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
We show that Odd Cycle Transversal and Vertex Multiway Cut admit determi...
read it

Caterpillars in ErdősHajnal
Let T be a tree such that all its vertices of degree more than two lie o...
read it

Subexponentialtime Algorithms for Maximum Independent Set in P_tfree and Broomfree Graphs
In algorithmic graph theory, a classic open question is to determine the...
read it

An improved FPT algorithm for Independent Feedback Vertex Set
We study the Independent Feedback Vertex Set problem  a variant of the ...
read it

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
The notion of treewidth, introduced by Robertson and Seymour in their se...
read it

Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set
Feedback Vertex Set is a classic combinatorial optimization problem that...
read it

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform QuasiWideness
The notions of bounded expansion and nowhere denseness not only offer ro...
read it

The ErdősHajnal conjecture for caterpillars and their complements
The celebrated ErdősHajnal conjecture states that for every proper here...
read it

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
The notion of Turing kernelization investigates whether a polynomialtim...
read it
Marcin Pilipczuk
is this you? claim profile