Skip to main content

Research Repository

Advanced Search

All Outputs (66)

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). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57

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.

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). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (229-242). https://doi.org/10.1007/978-3-030-83508-8_17

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. (2021). Steiner trees for hereditary graph classes. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (613-624). https://doi.org/10.1007/978-3-030-61792-9_48

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). Computing subset transversals in H-free graphs. In I. Adler, & H. Müller (Eds.), WG 2020: Graph-Theoretic Concepts in Computer Science (187-199). https://doi.org/10.1007/978-3-030-60440-0_15

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.

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest (2020)
Journal Article
Dabrowski, K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., & Rzążewski, P. (2020). On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica, 82(10), 2841-2866. https://doi.org/10.1007/s00453-020-00706-6

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL by showing that they can be solved in polynomial time... Read More about On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

Independent transversals versus transversals (2019)
Presentation / Conference Contribution
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals.

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two... Read More about Independent transversals versus transversals.

On cycle transversals and their connected variants in the absence of a small linear forest (2019)
Presentation / Conference Contribution
Feghali, C., Johnson, M., Paesani, G., & Paulusma, D. (2019). On cycle transversals and their connected variants in the absence of a small linear forest. In L. A. Gąsieniec, J. Jansson, & C. Levcopoulos (Eds.), Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings (258-273). https://doi.org/10.1007/978-3-030-25027-0_18

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and Odd Cycle Transversal by showing that they can be solved in polynomial time... Read More about On cycle transversals and their connected variants in the absence of a small linear forest.

Connected vertex cover for (sP1+P5)-free graphs (2019)
Journal Article
Johnson, M., Paesani, G., & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica, 82(1), 20-40. https://doi.org/10.1007/s00453-019-00601-9

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-... Read More about Connected vertex cover for (sP1+P5)-free graphs.

Filling the complexity gaps for colouring planar and bounded degree graphs (2019)
Journal Article
Dabrowski, K., Dross, F., Johnson, M., & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory, 92(4), 377-393. https://doi.org/10.1002/jgt.22459

A colouring of a graphGVE=( ,)is a function→cV:{1, 2,...}such that≠cucv() ()for every∈uvE.Ak‐regular list assignment ofGis a functionLwith domainVsuch that for every∈uV,Lu()is asubset of{1, 2,...}of sizek. A colouringcofGrespects ak‐regular list assi... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy (2019)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. In Z. Friggstad, J. Sack, & M. R. Salavatipour (Eds.), Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings (181-195). https://doi.org/10.1007/978-3-030-24766-9_14

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H1 and H2. Schweitzer settled the complexity of this problem restricted to (H1;H2)-free graphs for a... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Clique-width for hereditary graph classes (2019)
Journal Article
Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class G is bounded by a constant, a wide range of problems that are NP-complete in general can be shown to be po... Read More about Clique-width for hereditary graph classes.