20 citations · 75 across the 44 of their papers we have counts for
21 papers · 1 filter
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. I…
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Catarina Carvalho, Florent Madelaine, Barnaby Martin +1
Let A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, we argue that if A satisfies the polynomially generated powers property (PGP) and…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split…
The complete classification for quantified equality constraints
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
We prove that QCSP is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP…
Depth lower bounds in Stabbing Planes for combinatorial principles
Stefan Dantchev, Nicola Galesi, Abdul Ghani +1
Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequal…
Hard Problems That Quickly Become Very Easy
Barnaby Martin, Daniël Paulusma, Siani Smith
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable fo…
QCSP monsters and the demise of the Chen Conjecture
Dmitriy Zhuk, Barnaby Martin
We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language , QCSP, where is a fin…
Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in -- an extension of Resolution working on -DNFs instead of clauses -- for families of contradictions given in the {\em un…
The complexity of disjunctive linear Diophantine constraints
Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1
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.
Surjective H-Colouring over Reflexive Digraphs
Benoit Larose, Barnaby Martin, Daniel Paulusma
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…
Surjective H-Colouring: New Hardness Results
Petr Golovach, Matthew Johnson. Barnaby Martin, Daniel Paulusma +1
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 when…
Constraint Satisfaction Problems around Skolem Arithmetic
Christian Glasser, Peter Jonsson, Barnaby Martin
We study interactions between Skolem Arithmetic and certain classes of Constraint Satisfaction Problems (CSPs). We revisit results of Glass er et al. in the context of CSPs and set…
From complexity to algebra and back: digraph classes, collapsibility and the PGP
Catarina Carvalho, Florent Madelaine, Barnaby Martin
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…
QCSP on partially reflexive cycles - the wavy line of tractability
Florent Madelaine, Barnaby Martin
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive cycles. We obtain a complexity-theoretic dichotomy: QCSP(H) is ei…
Constraint Satisfaction with Counting Quantifiers
Florent Madelaine, Barnaby Martin, Juraj Stacho
We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCS…
The Complexity of Surjective Homomorphism Problems -- a Survey
Manuel Bodirsky, Jan Kara, Barnaby Martin
We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction…
QCSP on partially reflexive forests
Barnaby Martin
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive forests. We obtain a complexity-theoretic dichotomy: QCSP(H) is e…
Low-level dichotomy for Quantified Constraint Satisfaction Problems
Barnaby Martin
Building on a result of Larose and Tesson for constraint satisfaction problems (CSP s), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B i…
Distance Constraint Satisfaction Problems
Manuel Bodirsky, Victor Dalmau, Barnaby Martin +2
We study the complexity of constraint satisfaction problems for templates that are first-order definable in , the integers with the successor relation. Assuming…
Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three
Barnaby Martin
We study the model checking problem, for fixed structures A, over positive equality-free first-order logic -- a natural generalisation of the non-uniform quantified constraint sati…
On the Complexity of a Derivative Chess Problem
Barnaby Martin
We introduce QUEENS, a derivative chess problem based on the classical n-queens problem. We prove that QUEENS is NP-complete, with respect to polynomial-time reductions.