5 citations · 11 across the 23 of their papers we have counts for
32 papers
Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs
Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen
The Chromatic Sum problem asks, given a graph and an integer , whether admits a colouring with sum . We study the complexity of Chromatic S…
Beyond Parents? Prediction Gaps in University Completion Using Population-Scale Networks and Flexible Machine Learning
Javier Garcia-Bernardo, Eva Jaspers, Weverthon Machado +2
How predictable is children's educational attainment from the wider social contexts in which they grow up, once parental background is known? Sociological research places household…
Colouring Probe -Free Graphs
Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen
The NP-complete problems Colouring and k-Colouring ) are well studied on -free graphs, i.e., graphs that do not contain some fixed graph as an induced subgraph. We…
The Complexity of Diameter on H-free graphs
Jelle J. Oostveen, Daniël Paulusma, Erik Jan van Leeuwen
The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter f…
The Parameterised Complexity of Integer Multicommodity Flow
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen +2
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths…
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin +5
We study Steiner Forest on -subgraph-free graphs, that is, graphs that do not contain some fixed graph as a (not necessarily induced) subgraph. We are motivated by a recent…
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Matthew Johnson, Barnaby Martin, Sukanya Pandey +3
For any finite set of graphs, a graph is -subgraph-free if it does not contain any of as a subgraph. In recent work…
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
Vadim Lozin, Barnaby Martin, Sukanya Pandey +4
For a fixed set of graphs, a graph is -subgraph-free if does not contain any as a (not necessarily induced) subgraph. A recently propo…
Complexity Framework For Forbidden Subgraphs I: The Framework
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen +4
For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. T…
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…
Parameterized Complexity of Streaming Diameter and Connectivity Problems
Jelle J. Oostveen, Erik Jan van Leeuwen
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of si…
Few Induced Disjoint Paths for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer , th…
Induced Disjoint Paths and Connected Subgraphs for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. The Induced Disjoint Paths…
Streaming Deletion Problems Parameterized by Vertex Cover
Jelle J. Oostveen, Erik Jan van Leeuwen
Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a…
Disjoint Paths and Connected Subgraphs for H-Free Graphs
Walter Kern, Barnaby Martin, Daniël Paulusma +2
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We deter…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen
The Planar Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a…
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen
We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answ…
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph and a family of objects, each being a co…
Fast Dynamic Programming on Graph Decompositions
Johan M. M. van Rooij, Hans L. Bodlaender, Erik Jan van Leeuwen +2
In this paper, we consider tree decompositions, branch decompositions, and clique decompositions. We improve the running time of dynamic programming algorithms on these graph decom…
Algorithms and Bounds for Very Strong Rainbow Coloring
L. Sunil Chandran, Anita Das, Davis Issac +1
A well-studied coloring problem is to assign colors to the edges of a graph so that, for every pair of vertices, all edges of at least one shortest path between them receive di…
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A graph is a -graph if can be bipartitioned into and such that satisfies property and satisfies property . The $(Π_{A},Π_{B})…
Approximation and parameterized algorithms for geometric independent set with shrinking
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappin…