Skip to main content

Research Repository

Advanced Search

Professor Daniel Paulusma's Outputs (311)

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

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius (2023)
Presentation / Conference Contribution
Lucke, F., Paulusma, D., & Ries, B. (2023, August). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity re... Read More about Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.