Skip to main content

Research Repository

Advanced Search

All Outputs (85)

Complexity framework for forbidden subgraphs I: The framework (2025)
Journal Article
Johnson, M., Martin, B., Oostveen, J. .., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (online). Complexity framework for forbidden subgraphs I: The framework. Algorithmica, 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.

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.

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.

The Complexity of Matching Games: A Survey (2023)
Journal Article
Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of m... Read More about The Complexity of Matching Games: A Survey.

"Send a Soldier to Parliament": Ex-servicemen, Masculinity, and the Legacies of the Great War in Liberal Electoral and Parliamentary Politics (2023)
Journal Article
Johnson, M. (2023). "Send a Soldier to Parliament": Ex-servicemen, Masculinity, and the Legacies of the Great War in Liberal Electoral and Parliamentary Politics. Journal of British Studies, 62(3), 739 - 766. https://doi.org/10.1017/jbr.2022.233

The spectacular collapse of the Liberal Party in Britain has often been regarded as the result of a crisis in Liberal values, supposedly provoked by the unprecedented militarization of British society during the Great War. However, this interpretatio... Read More about "Send a Soldier to Parliament": Ex-servicemen, Masculinity, and the Legacies of the Great War in Liberal Electoral and Parliamentary Politics.

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.

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.

Computing weighted subset transversals in H-free graphs (2021)
Presentation / Conference Contribution
Brettell, N., Johnson, M., & Paulusma, D. (2021, August). Computing weighted subset transversals in H-free graphs. Presented at WADS 2021, Halifax, Nova Scotia

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

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration (2021)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109. https://doi.org/10.1002/jgt.22683

We continue research into a well-studied family of problems that ask whether the vertices of a given graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We consider the ca... Read More about Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration.

What graphs are 2-dot product graphs? (2021)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2021). What graphs are 2-dot product graphs?. International Journal of Computational Geometry and Applications, 31(01), 1-16. https://doi.org/10.1142/s0218195921500011

Let d ≥ 1 be an integer. From a set of d-dimensional vectors, we obtain a d-dot product graph by letting each vector a u correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product a u · a v ≥ t, for s... Read More about What graphs are 2-dot product graphs?.

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective (2021)
Journal Article
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to -... Read More about Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective.

Steiner trees for hereditary graph classes (2020)
Presentation / Conference Contribution
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (... Read More about Steiner trees for hereditary graph classes.

Computing subset transversals in H-free graphs (2020)
Presentation / Conference Contribution
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020, December). Computing subset transversals in H-free graphs. Presented at WG 2020, Leeds, England

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.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy (2020)
Journal Article
Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852. https://doi.org/10.1007/s00453-020-00747-x

We resolve the computational complexity of GRAPH ISOMORPHISM for classes of graphs characterized by two forbidden induced subgraphs H_{1} and H_2 for all but six pairs (H_1,H_2). Schweitzer had previously shown that the number of open cases was finit... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Clique-width for graph classes closed under complementation (2020)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We study the boundedness of cliq... Read More about Clique-width for graph classes closed under complementation.