All Outputs (5)

Consistency for counting quantifiers (2018)
Conference Proceeding
Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (11:1-11:13). https://doi.org/10.4230/lipics.mfcs.2018.11

We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach f... Read More about Consistency for counting quantifiers.

The complexity of disjunctive linear Diophantine constraints (2018)
Conference Proceeding
Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018). The complexity of disjunctive linear Diophantine constraints. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (33:1-33:16). https://doi.org/10.4230/lipics.mfcs.2018.33

We study the Constraint Satisfaction Problem CSP( A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.

Classification Transfer for Qualitative Reasoning Problems (2018)
Conference Proceeding
Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018). Classification Transfer for Qualitative Reasoning Problems. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) (1256-1262). https://doi.org/10.24963/ijcai.2018/175

We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitiv... Read More about Classification Transfer for Qualitative Reasoning Problems.

Surjective H-Colouring over Reflexive Digraphs (2018)
Conference Proceeding
Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (49:1-49:14). https://doi.org/10.4230/lipics.stacs.2018.49

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.

Disconnected Cuts in Claw-free Graphs (2018)
Conference Proceeding
Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018) (61:1-61:14). https://doi.org/10.4230/lipics.esa.2018.61

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut. It is known that Disconnected Cut is NP-hard on general graphs, while polynomial-... Read More about Disconnected Cuts in Claw-free Graphs.