Skip to main content

Research Repository

Advanced Search

Outputs (58)

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.