Source author record

Paul Bonsma

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an $O((m+n)\log n)$ algorithm for finding a canonical version of such a stable colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.

preprint2014arXiv

Independent Set Reconfiguration in Cographs

We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets $I$ and $J$ of a graph $G$ , both of size at least $k$ , is it possible to transform $I$ into $J$ by adding and removing vertices one-by-one, while maintaining an independent set of size at least $k$ throughout? This problem is known to be PSPACE-hard in general. For the case that $G$ is a cograph (i.e. $P_4$ -free graph) on $n$ vertices, we show that it can be solved in time $O(n^2)$ , and that the length of a shortest reconfiguration sequence from $I$ to $J$ is bounded by $4n-2k$ , if such a sequence exists. More generally, we show that if $X$ is a graph class for which (i) TAR-Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in $X$ using disjoint union and complete join operations. Chordal graphs are given as an example of such a class $X$ .

preprint2014arXiv

Reconfiguring Independent Sets in Claw-Free Graphs

We present a polynomial-time algorithm that, given two independent sets in a claw-free graph $G$ , decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex $v$ from the current independent set $S$ and to add a new vertex $w$ (not in $S$ ) such that the result is again an independent set. We also consider the more restricted model where $v$ and $w$ have to be adjacent.

preprint2014arXiv

The Complexity of Bounded Length Graph Recoloring

We study the following question: Given are two $k$ -colorings $α$ and $β$ of a graph $G$ on $n$ vertices, and integer $\ell$ . The question is whether $α$ can be modified into $β$ , by recoloring vertices one at a time, while maintaining a $k$ -coloring throughout, and using at most $\ell$ such recoloring steps. This problem is weakly PSPACE-hard for every constant $k\ge 4$ . We show that it is also strongly NP-hard for every constant $k\ge 4$ . On the positive side, we give an $O(f(k,\ell) n^{O(1)})$ algorithm for the problem, for some computable function $f$ . Hence the problem is fixed-parameter tractable when parameterized by $k+\ell$ . Finally, we show that the problem is W[1]-hard (but in XP) when parameterized only by $\ell$ .

preprint2012arXiv

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

In the unsplittable flow problem on a path, we are given a capacitated path $P$ and $n$ tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks, such that for each edge $e$ of $P$ , the total demand of selected tasks that use $e$ does not exceed the capacity of $e$ . This is a well-studied problem that has been studied under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of $O(\log n)$ . The approximation ratio of our algorithm is $7+ε$ for any $ε>0$ . We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves a special case of the maximum weight independent set of rectangles problem to optimality. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a $(2+ε)$ -approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either~1,~2, or~3.

preprint2012arXiv

Rerouting shortest paths in planar graphs

A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.

preprint2012arXiv

The Complexity of Rerouting Shortest Paths

The Shortest Path Reconfiguration problem has as input a graph G (with unit edge lengths) with vertices s and t, and two shortest st-paths P and Q. The question is whether there exists a sequence of shortest st-paths that starts with P and ends with Q, such that subsequent paths differ in only one vertex. This is called a rerouting sequence. This problem is shown to be PSPACE-complete. For claw-free graphs and chordal graphs, it is shown that the problem can be solved in polynomial time, and that shortest rerouting sequences have linear length. For these classes, it is also shown that deciding whether a rerouting sequence exists between all pairs of shortest st-paths can be done in polynomial time. Finally, a polynomial time algorithm for counting the number of isolated paths is given.

preprint2011arXiv

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

The Subgraph Isomorphism problem asks, given a host graph G on n vertices and a pattern graph P on k vertices, whether G contains a subgraph isomorphic to P. The restriction of this problem to planar graphs has often been considered. After a sequence of improvements, the current best algorithm for planar graphs is a linear time algorithm by Dorn (STACS '10), with complexity $2^{O(k)} O(n)$ . We generalize this result, by giving an algorithm of the same complexity for graphs that can be embedded in surfaces of bounded genus. At the same time, we simplify the algorithm and analysis. The key to these improvements is the introduction of surface split decompositions for bounded genus graphs, which generalize sphere cut decompositions for planar graphs. We extend the algorithm for the problem of counting and generating all subgraphs isomorphic to P, even for the case where P is disconnected. This answers an open question by Eppstein (SODA '95 / JGAA '99).

preprint2010arXiv

Feedback Vertex Set in Mixed Graphs

A mixed graph is a graph with both directed and undirected edges. We present an algorithm for deciding whether a given mixed graph on $n$ vertices contains a feedback vertex set (FVS) of size at most $k$ , in time $2^{O(k)}k! O(n^4)$ . This is the first fixed parameter tractable algorithm for FVS that applies to both directed and undirected graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Paul Bonsma

Research overview

Is this your work?

9 publications

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

Independent Set Reconfiguration in Cographs

Reconfiguring Independent Sets in Claw-Free Graphs

The Complexity of Bounded Length Graph Recoloring

A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

Rerouting shortest paths in planar graphs

The Complexity of Rerouting Shortest Paths

Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

Feedback Vertex Set in Mixed Graphs

See the researcher in context

Building this map preview