All Outputs (4)

Surjective H-Colouring over reflexive digraphs (2018)
Journal Article
Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality,... Read More about Surjective H-Colouring over reflexive digraphs.

On the Complexity of the Model Checking Problem (2018)
Journal Article
Madelaine, F. R., & Martin, B. D. (2018). On the Complexity of the Model Checking Problem. SIAM Journal on Computing, 47(3), 769-797. https://doi.org/10.1137/140965715

The complexity of the model checking problem for various fragments of first-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by ∃ and ∧ and that induced by ∀, ∃, and ∧, which are better k... Read More about On the Complexity of the Model Checking Problem.

Surjective H-colouring: New hardness results (2018)
Journal Article
Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-colouring: New hardness results.

Discrete Temporal Constraint Satisfaction Problems (2018)
Journal Article
Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM, 65(2), Article 9. https://doi.org/10.1145/3154832

A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every... Read More about Discrete Temporal Constraint Satisfaction Problems.