Skip to main content

Research Repository

Advanced Search

All Outputs (58)

The complexity of disjunctive linear Diophantine constraints (2018)
Presentation / Conference Contribution
Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018, August). The complexity of disjunctive linear Diophantine constraints. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

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)
Presentation / Conference Contribution
Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018, July). Classification Transfer for Qualitative Reasoning Problems. Presented at IJCAI-ECAI 2018, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence., Stockholm, Sweden

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.

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.

Surjective H-Colouring over Reflexive Digraphs (2018)
Presentation / Conference Contribution
Larose, B., Martin, B., & Paulusma, D. (2023, February). Surjective H-Colouring over Reflexive Digraphs. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France

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)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018, August). Disconnected Cuts in Claw-free Graphs. Presented at 26th Annual European Symposium on Algorithms (ESA 2018)., Helsinki, Finland

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.

Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic (2017)
Journal Article
Glaßer, C., Jonsson, P., & Martin, B. (2017). Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science, 703, 18-36. https://doi.org/10.1016/j.tcs.2017.08.025

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [1] in the context of CSPs and settle the major open question from that pap... Read More about Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic.

The complexity of quantified constraints using the algebraic formulation (2017)
Presentation / Conference Contribution
Carvalho, C., Martin, B., Zhuk, D., Larsen, K. G., Bodlaender, H. L., & Raskin, J.-F. (2017, December). The complexity of quantified constraints using the algebraic formulation. Presented at Mathematical Foundation of Computer Science, Aalborg, Denmark

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove... Read More about The complexity of quantified constraints using the algebraic formulation.

The packing chromatic number of the infinite square lattice is between 13 and 15 (2017)
Journal Article
Martin, B., Raimondi, F., Chen, T., & Martin, J. (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225, 136-142. https://doi.org/10.1016/j.dam.2017.03.013

Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss the merits of SAT-solving for this kind of problem as well as compare... Read More about The packing chromatic number of the infinite square lattice is between 13 and 15.

Quantified Constraint Satisfaction Problem on semicomplete digraphs (2017)
Journal Article
Đapić, P., Marković, P., & Martin, B. (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic, 18(1), Article 2. https://doi.org/10.1145/3007899

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(H) is either in P, is NP-complete, or is Pspace-complete. The largest part of our... Read More about Quantified Constraint Satisfaction Problem on semicomplete digraphs.

The complexity of counting quantifiers on equality languages (2017)
Journal Article
Martin, B., Pongrácz, A., & Wrona, M. (2017). The complexity of counting quantifiers on equality languages. Theoretical Computer Science, 670, 56-67. https://doi.org/10.1016/j.tcs.2017.01.022

An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existe... Read More about The complexity of counting quantifiers on equality languages.

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (2016)
Presentation / Conference Contribution
Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016, July). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Presented at 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Rome, Italy

For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with do... Read More about Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP (2015)
Presentation / Conference Contribution
Carvalho, C., Madelaine, F. R., & Martin, B. (2015, July). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. Presented at 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, Kyoto, Japan

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Buildin... Read More about From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP.

Constraint Satisfaction Problems over the Integers with Successor (2015)
Presentation / Conference Contribution
Bodirsky, M., Martin, B., & Mottet, A. (2015, July). Constraint Satisfaction Problems over the Integers with Successor. Presented at Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Kyoto, Japan

A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z;succ)(Z;succ), i.e., over the integers with the successor function. Our main... Read More about Constraint Satisfaction Problems over the Integers with Successor.

The computational complexity of disconnected cut and 2K2-partition (2014)
Journal Article
Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This pr... Read More about The computational complexity of disconnected cut and 2K2-partition.

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems (2012)
Journal Article
Dantchev, S., & Martin, B. (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity, 22(1), 191-213. https://doi.org/10.1007/s00037-012-0049-1

We prove a dichotomy theorem for the rank of propositional contradictions, uniformly generated from first-order sentences, in both the Lovász-Schrijver (LS) and Sherali-Adams (SA) refutation systems. More precisely, we first show that the proposition... Read More about Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems.