Source author record

Daniel Paulusma

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

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO Computational Complexity

Catalog footprint

Research overview

12works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The complexity of L(p,q)-Edge-Labelling

We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially classified. We complete this study for all nonnegative p and q, by showing that, whenever (p,q) is not (0,0), L(p,q)-Edge-Labelling problem is NP-complete. We do this by proving that for all nonnegative p and q, except p=q=0, there exists an integer k so that L(p,q)-Edge-k-Labelling is NP-complete.

preprint2021arXiv

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

For $k\geq 1$ , a $k$ -colouring $c$ of $G$ is a mapping from $V(G)$ to $\{1,2,\ldots,k\}$ such that $c(u)\neq c(v)$ for any two non-adjacent vertices $u$ and $v$ . The $k$ -Colouring problem is to decide if a graph $G$ has a $k$ -colouring. For a family of graphs ${\cal H}$ , a graph $G$ is ${\cal H}$ -free if $G$ does not contain any graph from ${\cal H}$ as an induced subgraph. Let $C_s$ be the $s$ -vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of $3$ -Colouring for $(C_3,\ldots,C_s)$ -free graphs and $H$ -free graphs where $H$ is some polyad. Here, we prove for certain small values of $s$ that $3$ -Colouring is polynomial-time solvable for $C_s$ -free graphs of diameter $2$ and $(C_4,C_s)$ -free graphs of diameter $2$ . In fact, our results hold for the more general problem List $3$ -Colouring. We complement these results with some hardness result for diameter $4$ .

preprint2021arXiv

QCSP on Reflexive Tournaments

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i<j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.

preprint2020arXiv

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective

We prove that the class of $(K_t,sP_1+P_5)$ -free graphs has bounded mim-width for every $s\geq 0$ and $t\geq 1$ , and that there is a polynomial-time algorithm that, given a graph in the class, computes a branch decomposition of constant mim-width. A large number of \NP-complete graph problems become polynomial-time solvable on graph classes with bounded mim-width and for which a branch decomposition is quickly computable. The $k$ -Colouring problem is an example of such a problem. For this problem, we may assume that the input graph is $K_{k+1}$ -free. Then, as a consequence of our result, we obtain a new proof for the known result that for every fixed $k\geq 1$ and $s\geq 0$ , $k$ -Colouring is polynomial-time solvable for $(sP_1+P_5)$ -free graphs. In fact, our findings show that the underlying reason for this polynomial-time algorithm is that the class has bounded mim-width.

preprint2016arXiv

New Bounds for the Snake-in-the-Box Problem

The Snake-in-the-Box problem is that of finding a longest induced path in an $n$ -dimensional hypercube. We prove new lower bounds for the values $n\in \{11,12,13\}$ . The Coil-in-the-Box problem is that of finding a longest induced cycle in an $n$ -dimensional hypercube. We prove new lower bounds for the values $n\in \{12,13\}$ .

preprint2015arXiv

Editing to a Planar Graph of Given Degrees

We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$ , a weight function $w\colon V\cup E\rightarrow \mathbb{N}$ , a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $δ\colon V\rightarrow \mathbb{N}_0$ , together with three integers $k_v, k_e$ and $C$ . The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most $C$ and every non-deleted vertex $v$ has degree $δ(v)$ in the resulting graph $G'$ . We also consider the variant in which $G'$ must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by $k_v+k_e$ . We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by $k_v+k_e$ .

preprint2015arXiv

Kempe Equivalence of Colourings of Cubic Graphs

Given a graph $G=(V,E)$ and a proper vertex colouring of $G$ , a Kempe chain is a subset of $V$ that induces a maximal connected subgraph of $G$ in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by exchanging the colours of vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe changes. A conjecture of Mohar asserts that, for $k \geq 3$ , all $k$ -colourings of $k$ -regular graphs that are not complete are Kempe equivalent. We address the case $k=3$ by showing that all $3$ -colourings of a cubic graph $G$ are Kempe equivalent unless $G$ is the complete graph $K_4$ or the triangular prism.

preprint2014arXiv

Induced Disjoint Paths in Claw-Free Graphs

Paths P1,...,Pk in a graph G=(V,E) are said to be mutually induced if for any 1 <= i < j <= k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti for i=1,...,k. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are proven to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP \subseteq coNP/poly. Moreover, the problem becomes NP-complete, even when k=2, for the more general class of K_1,4-free graphs. Finally, we show that the n^O(k)-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.

preprint2014arXiv

The Computational Complexity of Disconnected Cut and 2K2-Partition

For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K2-partition, testing if a graph allows a vertex-surjective homomorphism to the reflexive 4-cycle and testing if a graph has a spanning subgraph that consists of at most two bicliques. Hence, as an immediate consequence, these three decision problems are NP-complete as well. This settles an open problem frequently posed in each of the four settings.

preprint2012arXiv

Obtaining Planarity by Contracting Few Edges

The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.

preprint2010arXiv

Contracting planar graphs to contractions of triangulations

For every graph $H$ , there exists a polynomial-time algorithm deciding if a planar input graph $G$ can be contracted to~ $H$ . However, the degree of the polynomial depends on the size of $H$ . In this paper, we identify a class of graphs $\cal C$ such that for every $H \in \cal C$ , there exists an algorithm deciding in time $f(|V(H)|) \cdot |V(G)|^{\bigO{1}}$ whether a planar graph $G$ can be contracted to~ $H$ . (The function $f(\cdot)$ does not depend on $G$ .) The class $\cal C$ is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph $H \in \cal C$ if and only if there exists a constant $c_H$ such that if the tree-width of a graph is at least $c_H$ , it contains $H$ as a contraction. We also provide a characterization of $\cal C$ in terms of minimal forbidden contractions.

preprint2010arXiv

The k-in-a-path problem for claw-free graphs

Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial time on claw-free graphs, when k is not part of the input but an arbitrarily fixed integer.

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.

Daniel Paulusma

Research overview

Is this your work?

12 publications

The complexity of L(p,q)-Edge-Labelling

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

QCSP on Reflexive Tournaments

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective

New Bounds for the Snake-in-the-Box Problem

Editing to a Planar Graph of Given Degrees

Kempe Equivalence of Colourings of Cubic Graphs

Induced Disjoint Paths in Claw-Free Graphs

The Computational Complexity of Disconnected Cut and 2K2-Partition

Obtaining Planarity by Contracting Few Edges

Contracting planar graphs to contractions of triangulations

The k-in-a-path problem for claw-free graphs

See the researcher in context

Building this map preview

Daniel Paulusma

Research overview

Is this your work?

12 publications

The complexity of L(p,q)-Edge-Labelling

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

QCSP on Reflexive Tournaments

Colouring (sP1+P5)(sP_1+P_5)(sP1​+P5​)-Free Graphs: a Mim-Width Perspective

New Bounds for the Snake-in-the-Box Problem

Editing to a Planar Graph of Given Degrees

Kempe Equivalence of Colourings of Cubic Graphs

Induced Disjoint Paths in Claw-Free Graphs

The Computational Complexity of Disconnected Cut and 2K2-Partition

Obtaining Planarity by Contracting Few Edges

Contracting planar graphs to contractions of triangulations

The k-in-a-path problem for claw-free graphs

See the researcher in context

Building this map preview

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective