Outputs (8)

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034

For a fixed integer, the k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an ind... Read More about Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.

Partitioning H-free graphs of bounded diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, Star, and Injective Colouring: Bounding the diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738

We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices... Read More about Acyclic, Star, and Injective Colouring: Bounding the diameter.

QCSP on reflexive tournaments (2022)
Journal Article
Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components H1,…,Hn so that ther... Read More about QCSP on reflexive tournaments.

Colouring graphs of bounded diameter in the absence of small cycles (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H-f... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Journal Article
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Dis... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Hard problems that quickly become very easy (2021)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213

A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all g... Read More about Hard problems that quickly become very easy.