Skip to main content

Research Repository

Advanced Search

Outputs (315)

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem (2025)
Journal Article
Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. Journal of Computer and System Sciences, 154, Article 103682. https://doi.org/10.1016/j.jcss.2025.103682

We study Steiner Forest on H-subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. In contrast to the related Steiner Tree problem, Steiner Forest falls outside a recent framework that c... Read More about Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.

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.