Skip to main content

Research Repository

Advanced Search

All Outputs (26)

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.

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.