The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4

The L(p, q)-EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p, q)-Edge-Labelling.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Finding matching cuts in H-free graphs (2022)
Conference Proceeding
Lucke, F., Paulusma, D., & Ries, B. (2022). Finding matching cuts in H-free graphs. In S. W. Bae, & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) (22:1-22:16). https://doi.org/10.4230/lipics.isaac.2022.22

The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed... Read More about Finding matching cuts in H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Conference Proceeding
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7

Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs... Read More about Few induced disjoint paths for H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024

Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices contains k mutu... Read More about Few induced disjoint paths for H-free graphs.

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs (2022)
Journal Article
Paesani, G., Paulusma, D., & Rzążwski, P. (2022). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM Journal on Discrete Mathematics, 36(4), 2453-2472. https://doi.org/10.1137/22m1468864

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are pol... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs.

Classifying Subset Feedback Vertex Set for H-free graphs (2022)
Conference Proceeding
Paesani, G., Paulusma, D., & Rzążewski, P. (2022). Classifying Subset Feedback Vertex Set for H-free graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (412-424). https://doi.org/10.1007/978-3-031-15914-5_30

In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also... Read More about Classifying Subset Feedback Vertex Set for H-free graphs.

An algorithmic framework for locally constrained homomorphisms (2022)
Conference Proceeding
Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022). An algorithmic framework for locally constrained homomorphisms. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (114-128). https://doi.org/10.1007/978-3-031-15914-5_9

A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decision... Read More about An algorithmic framework for locally constrained homomorphisms.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2022)
Conference Proceeding
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (398-411). https://doi.org/10.1007/978-3-031-15914-5_29

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

On the complexity of matching cut for graphs of bounded radius and H-free graphs (2022)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2022). On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936, 33-42. https://doi.org/10.1016/j.tcs.2022.09.014

For a connected graph G = (V , E), a matching M ⊆ E is a matching cut of G if G − M is disconnected. It is known that for an integer d, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most d if d... Read More about On the complexity of matching cut for graphs of bounded radius and H-free graphs.

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034

For a fixed integer, the k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an ind... Read More about Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.

Partitioning H-free graphs of bounded diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, Star, and Injective Colouring: Bounding the diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738

We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices... Read More about Acyclic, Star, and Injective Colouring: Bounding the diameter.

Computing Balanced Solutions for Large International Kidney Exchange Schemes (2022)
Conference Proceeding
Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022). Computing Balanced Solutions for Large International Kidney Exchange Schemes. In AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (82-90)

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countr... Read More about Computing Balanced Solutions for Large International Kidney Exchange Schemes.

Computing weighted subset odd cycle transversals in H-free graphs (2022)
Journal Article
Brettell, N., Johnson, M., & Paulusma, D. (2022). Computing weighted subset odd cycle transversals in H-free graphs. Journal of Computer and System Sciences, 128, 71-85. https://doi.org/10.1016/j.jcss.2022.03.002

For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of... Read More about Computing weighted subset odd cycle transversals in H-free graphs.

QCSP on reflexive tournaments (2022)
Journal Article
Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069

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 H1,…,Hn so that ther... Read More about QCSP on reflexive tournaments.

Colouring graphs of bounded diameter in the absence of small cycles (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two 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 H, a graph G is H-f... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

The Complexity of L(p,q)-Edge-Labelling (2022)
Conference Proceeding
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Computing subset transversals in H-free graphs (2021)
Journal Article
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science, 902, 76-92. https://doi.org/10.1016/j.tcs.2021.12.010

we study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph... Read More about Computing subset transversals in H-free graphs.

Tree pivot-minors and linear rank-width (2021)
Journal Article
Dabrowski, K., Dross, F., Jeong, J., Kante, M., Kwon, O., Oum, S., & Paulusma, D. (2021). Tree pivot-minors and linear rank-width. SIAM Journal on Discrete Mathematics, 35(4), 2922-2945. https://doi.org/10.1137/21m1402339

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree T, the class of graphs that do not contain T as a minor has bounded path-width. For... Read More about Tree pivot-minors and linear rank-width.