Skip to main content

Research Repository

Advanced Search

Professor Daniel Paulusma's Outputs (314)

Acyclic, star and injective colouring: A complexity picture for H-free graphs (2025)
Journal Article
Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective... Read More about Acyclic, star and injective colouring: A complexity picture for H-free graphs.

Matching Cuts in Graphs of High Girth and H-Free Graphs (2025)
Journal Article
Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (online). Matching Cuts in Graphs of High Girth and H-Free Graphs. Algorithmica, https://doi.org/10.1007/s00453-025-01318-8

The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. B... Read More about Matching Cuts in Graphs of High Girth and H-Free Graphs.

Comparing width parameters on graph classes (2025)
Journal Article
Brettell, N., Munaro, A., Paulusma, D., & Yang, S. (2025). Comparing width parameters on graph classes. European Journal of Combinatorics, 127, Article 104163. https://doi.org/10.1016/j.ejc.2025.104163

We study how the relationship between non-equivalent width parameters changes once we restrict to some special graph class. As width parameters we consider treewidth, clique-width, twin-width, mim-width, sim-width and tree-independence number, wherea... Read More about Comparing width parameters on graph classes.

The Complexity of Diameter on H-free Graphs (2025)
Presentation / Conference Contribution
Oostveen, J. J., Paulusma, D., & van Leeuwen, E. J. (2024, June). The Complexity of Diameter on H-free Graphs. Presented at WG 2024, Gozd Martuljek, Slovenia

Complexity Framework for Forbidden Subgraphs I: The Framework (2025)
Journal Article
Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2

For a set of graphs H, a graph G is H-subgraph-free if G does not contain any graph from H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for H-subgraph-free graphs. Namely, a grap... Read More about Complexity Framework for Forbidden Subgraphs I: The Framework.

Maximizing Matching Cuts (2024)
Book Chapter
Le, V. B., Lucke, F., Paulusma, D., & Ries, B. (2024). Maximizing Matching Cuts. In P. M. Pardalos, & O. A. Prokopyev (Eds.), Encyclopedia of Optimization (1-10). Springer Nature. https://doi.org/10.1007/978-3-030-54621-2_898-1

Graph cut problems belong to a well-studied class of classical graph problems related to network connectivity, which is a central concept within theoretical computer science.

Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs (2024)
Presentation / Conference Contribution
Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024

For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are... Read More about Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs.

Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs (2024)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland

It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degr... Read More about Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs.

Computing balanced solutions for large international kidney exchange schemes (2024)
Journal Article
Benedek, M., Biró, P., Paulusma, D., & Ye, X. (2024). Computing balanced solutions for large international kidney exchange schemes. Autonomous Agents and Multi-Agent Systems, 38(1), Article 18. https://doi.org/10.1007/s10458-024-09645-w

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 Subset Vertex Covers in H-Free Graphs (2023)
Presentation / Conference Contribution
Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., & van Leeuwen, E. J. (2023, September). Computing Subset Vertex Covers in H-Free Graphs. Presented at FCT 2023: Fundamentals of Computation Theory, Trier, Germany