Logic, computation and constraint satisfaction. - Barnaby Martin (2005)

Towards a Trichotomy for Quantified H-Coloring. - Barnaby Martin; Florent R. Madelaine (CiE, 2006)

Dichotomies and Duality in First-order Model Checking Problems - Barnaby Martin (CoRR, 2006)

Hierarchies in Fragments of Monadic Strict NP. - Barnaby Martin; Florent R. Madelaine (CiE, 2007)

On the Complexity of a Derivative Chess Problem - Barnaby Martin (CoRR, 2007)

Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution. - Stefan S. Dantchev; Barnaby Martin; Stefan Szeider (Electron. Colloquium Comput. Complex., 2007)

First-Order Model Checking Problems Parameterized by the Model. - Barnaby Martin (CiE, 2008)

Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three - Barnaby Martin (CoRR, 2008)

The complexity of positive first-order logic without equality II: The four-element case. - Barnaby Martin; Jos Martin (The Constraint Satisfaction Problem: Complexity and Approximability, 2009)

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction - Manuel Bodirsky; Martin Hils; Barnaby Martin (Log. Methods Comput. Sci., 2009)

Tight rank lower bounds for the Sherali-Adams proof system. - Stefan S. Dantchev; Barnaby Martin; Mark Nicholas Charles Rhodes (Theor. Comput. Sci., 2009)

The Lattice Structure of Sets of Surjective Hyper-Operations. - Barnaby Martin (CP, 2010)

Distance Constraint Satisfaction Problems. - Manuel Bodirsky; Víctor Dalmau; Barnaby Martin; Michael Pinsker (MFCS, 2010)

QCSP on Partially Reflexive Forests. - Barnaby Martin (CP, 2011)

The Computational Complexity of Disconnected Cut and 2K 2-Partition. - Barnaby Martin; Daniël Paulusma (CP, 2011)

A Tetrachotomy for Positive First-Order Logic without Equality. - Florent R. Madelaine; Barnaby Martin (LICS, 2011)

Parameterized Proof Complexity. - Stefan S. Dantchev; Barnaby Martin; Stefan Szeider (Comput. Complex., 2011)

The Computational Complexity of Disconnected Cut and 2K2-Partition - Barnaby Martin; Daniël Paulusma (CoRR, 2011)

Low-level dichotomy for quantified constraint satisfaction problems. - Barnaby Martin (Inf. Process. Lett., 2011)

Containment, Equivalence and Coreness from CSP to QCSP and Beyond. - Florent R. Madelaine; Barnaby Martin (CP, 2012)

Finding vertex-surjective graph homomorphisms. - Petr A. Golovach; Bernard Lidický; Barnaby Martin; Daniël Paulusma (Acta Informatica, 2012)

The limits of tractability in Resolution-based propositional proof systems. - Stefan S. Dantchev; Barnaby Martin (Ann. Pure Appl. Log., 2012)

Parameterized Proof Complexity and W[1] - Barnaby Martin (CoRR, 2012)

The complexity of surjective homomorphism problems - a survey. - Manuel Bodirsky; Jan Kára; Barnaby Martin (Discret. Appl. Math., 2012)

Cutting Planes and the Parameter Cutwidth. - Stefan S. Dantchev; Barnaby Martin (Theory Comput. Syst., 2012)

The Complexity of Positive First-Order Logic without Equality. - Florent R. Madelaine; Barnaby Martin (ACM Trans. Comput. Log., 2012)

Parameterized Resolution with Bounded Conjunction. - Stefan S. Dantchev; Barnaby Martin (CSR, 2013)

QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability. - Florent R. Madelaine; Barnaby Martin (CSR, 2013)

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. - Stefan S. Dantchev; Barnaby Martin (Comput. Complex., 2013)

Relativisation makes contradictions harder for Resolution - Stefan S. Dantchev; Barnaby Martin (CoRR, 2013)

Constraint Satisfaction with Counting Quantifiers 2. - Barnaby Martin; Juraj Stacho (CSR, 2014)

QCSP on Semicomplete Digraphs. - Petar Dapic; Petar Markovic; Barnaby Martin (ICALP (1), 2014)

Relativization makes contradictions harder for Resolution. - Stefan S. Dantchev; Barnaby Martin (Ann. Pure Appl. Log., 2014)

First-Order Queries on Finite Abelian Groups. - Simone Bova; Barnaby Martin (CSL, 2015)

Constraint Satisfaction Problems over the Integers with Successor. - Manuel Bodirsky; Barnaby Martin; Antoine Mottet (ICALP (1), 2015)

From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. - Catarina Carvalho; Florent R. Madelaine; Barnaby Martin (LICS, 2015)

Quantified Constraints and Containment Problems. - Hubie Chen; Florent R. Madelaine; Barnaby Martin (Log. Methods Comput. Sci., 2015)

Constraint Satisfaction Problems around Skolem Arithmetic. - Christian Glaßer; Peter Jonsson; Barnaby Martin (CoRR, 2015)

The packing chromatic number of the infinite square lattice is less than or equal to 16. - Barnaby Martin; Franco Raimondi; Taolue Chen 001; Jos Martin (CoRR, 2015)

Switchability and collapsibility of Gap Algebras. - Barnaby Martin; Dmitriy Zhuk (CoRR, 2015)

The computational complexity of disconnected cut and 2K2-partition. - Barnaby Martin; Daniël Paulusma (J. Comb. Theory B, 2015)

Constraint Satisfaction with Counting Quantifiers. - Barnaby Martin; Florent R. Madelaine; Juraj Stacho (SIAM J. Discret. Math., 2015)

On the Chen Conjecture regarding the complexity of QCSPs. - Barnaby Martin (CoRR, 2016)

Report on BCTCS 2015. - Barnaby Martin (Bull. EATCS, 2016)

Distance constraint satisfaction problems. - Manuel Bodirsky; Víctor Dalmau; Barnaby Martin; Antoine Mottet; Michael Pinsker (Inf. Comput., 2016)

Quantified Constraints in Twenty Seventeen. - Barnaby Martin (The Constraint Satisfaction Problem, 2017)

The Complexity of Quantified Constraints Using the Algebraic Formulation. - Catarina Carvalho; Barnaby Martin; Dmitriy Zhuk (MFCS, 2017)

The complexity of quantified constraints. - Catarina Carvalho; Barnaby Martin; Dmitriy Zhuk (CoRR, 2017)

The packing chromatic number of the infinite square lattice is between 13 and 15. - Barnaby Martin; Franco Raimondi; Taolue Chen 001; Jos Martin (Discret. Appl. Math., 2017)

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. - Christian Glaßer; Peter Jonsson; Barnaby Martin (Theor. Comput. Sci., 2017)

The complexity of counting quantifiers on equality languages. - Barnaby Martin; András Pongrácz; Michal Wrona (Theor. Comput. Sci., 2017)

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs. - Petar Dapic; Petar Markovic; Barnaby Martin (ACM Trans. Comput. Log., 2017)

Classification Transfer for Qualitative Reasoning Problems. - Manuel Bodirsky; Peter Jonsson; Barnaby Martin; Antoine Mottet (IJCAI, 2018)

The Complexity of Disjunctive Linear Diophantine Constraints. - Manuel Bodirsky; Barnaby Martin; Marcello Mamino; Antoine Mottet (MFCS, 2018)

Consistency for Counting Quantifiers. - Florent R. Madelaine; Barnaby Martin (MFCS, 2018)

Resolution and the binary encoding of combinatorial principles. - Stefan S. Dantchev; Nicola Galesi; Barnaby Martin (Electron. Colloquium Comput. Complex., 2018)

Discrete Temporal Constraint Satisfaction Problems. - Manuel Bodirsky; Barnaby Martin; Antoine Mottet (J. ACM, 2018)

On the Complexity of the Model Checking Problem. - Florent R. Madelaine; Barnaby Martin (SIAM J. Comput., 2018)

Colouring H-Free Graphs of Bounded Diameter. - Barnaby Martin; Daniël Paulusma; Siani Smith (MFCS, 2019)

Surjective H-colouring: New hardness results. - Petr A. Golovach; Matthew Johnson 002; Barnaby Martin; Daniël Paulusma; Anthony Stewart (Comput., 2019)

Report on BCTCS & AlgoUK 2019. - Matthew Johnson 002; Barnaby Martin; George B. Mertzios; Daniël Paulusma (Bull. EATCS, 2019)

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. - Manuel Bodirsky; Barnaby Martin; Michael Pinsker; András Pongrácz (SIAM J. Comput., 2019)

Surjective H-Colouring over Reflexive Digraphs. - Benoît Larose; Barnaby Martin; Daniël Paulusma (ACM Trans. Comput. Theory, 2019)

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. - Jan Bok; Nikola Jedlicková; Barnaby Martin; Daniël Paulusma; Siani Smith (ESA, 2020)

Sherali-Adams and the Binary Encoding of Combinatorial Principles. - Stefan S. Dantchev; Abdul Ghani 001; Barnaby Martin (LATIN, 2020)

Disconnected cuts in claw-free graphs. - Barnaby Martin; Daniël Paulusma; Erik Jan van Leeuwen (J. Comput. Syst. Sci., 2020)

Injective Colouring for H-Free Graphs. - Jan Bok; Nikola Jedlicková; Barnaby Martin; Daniël Paulusma; Siani Smith (CSR, 2021)

Partitioning H-Free Graphs of Bounded Diameter. - Christoph Brause; Petr A. Golovach; Barnaby Martin; Daniël Paulusma; Siani Smith (ISAAC, 2021)

Disjoint Paths and Connected Subgraphs for H-Free Graphs. - Walter Kern; Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (IWOCA, 2021)

Acyclic, Star, and Injective Colouring: Bounding the Diameter. - Christoph Brause; Petr A. Golovach; Barnaby Martin; Daniël Paulusma; Siani Smith (WG, 2021)

The complete classification for quantified equality constraints. - Dmitriy Zhuk; Barnaby Martin (CoRR, 2021)

Depth lower bounds in Stabbing Planes for combinatorial principles. - Stefan S. Dantchev; Nicola Galesi; Abdul Ghani 001; Barnaby Martin (Electron. Colloquium Comput. Complex., 2021)

Few Induced Disjoint Paths for H-Free Graphs. - Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (ISCO, 2022)

Acyclic, Star, and Injective Colouring: Bounding the Diameter. - Christoph Brause; Petr A. Golovach; Barnaby Martin; Pascal Ochem; Daniël Paulusma; Siani Smith (Electron. J. Comb., 2022)

When bounds consistency implies domain consistency for regular counting constraints. - Barnaby Martin; Justin Pearson (Constraints An Int. J., 2022)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs. - Matthew Johnson 002; Barnaby Martin; Siani Smith; Sukanya Pandey; Daniël Paulusma; Erik Jan van Leeuwen (CoRR, 2022)

Complexity Framework For Forbidden Subgraphs. - Matthew Johnson 002; Barnaby Martin; Jelle J. Oostveen; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (CoRR, 2022)

Complexity Framework for Forbidden Subgraphs: When Hardness Is Not Preserved under Edge Subdivision. - Barnaby Martin; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (CoRR, 2022)

Colouring graphs of bounded diameter in the absence of small cycles. - Barnaby Martin; Daniël Paulusma; Siani Smith (Discret. Appl. Math., 2022)

The lattice and semigroup structure of multipermutations. - Catarina Carvalho; Barnaby Martin (Int. J. Algebra Comput., 2022)

Hard problems that quickly become very easy. - Barnaby Martin; Daniël Paulusma; Siani Smith (Inf. Process. Lett., 2022)

QCSP Monsters and the Demise of the Chen Conjecture. - Dmitriy Zhuk; Barnaby Martin (J. ACM, 2022)

Partitioning H-free graphs of bounded diameter. - Christoph Brause; Petr A. Golovach; Barnaby Martin; Daniël Paulusma; Siani Smith (Theor. Comput. Sci., 2022)

Disjoint paths and connected subgraphs for H-free graphs. - Walter Kern; Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (Theor. Comput. Sci., 2022)

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. - Barnaby Martin; Daniël Paulusma; Siani Smith (Theor. Comput. Sci., 2022)

QCSP on Reflexive Tournaments. - Benoît Larose; Barnaby Martin; Petar Markovic; Daniël Paulusma; Siani Smith; Stanislav Zivný (ACM Trans. Comput. Log., 2022)

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. - Matthew Johnson 002; Barnaby Martin; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (MFCS, 2023)

The complete classification for quantified equality constraints. - Dmitriy Zhuk; Barnaby Martin; Michal Wrona (SODA, 2023)

Few induced disjoint paths for H-free graphs. - Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (Theor. Comput. Sci., 2023)

The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation. - Catarina Carvalho; Florent R. Madelaine; Barnaby Martin; Dmitriy Zhuk (ACM Trans. Comput. Log., 2023)

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. - Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (Algorithmica, 2023)

The Complexity of L(p, q)-Edge-Labelling. - Gaétan Berthe; Barnaby Martin; Daniël Paulusma; Siani Smith (Algorithmica, 2023)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth. - Tala Eagling-Vose; Barnaby Martin; Daniël Paulusma; Siani Smith (CiE, 2024)

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. - Vadim V. Lozin; Barnaby Martin; Sukanya Pandey; Daniël Paulusma; Mark H. Siggers; Siani Smith; Erik Jan van Leeuwen (ISAAC, 2024)

Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. - Matthew Johnson 002; Barnaby Martin; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (SWAT, 2024)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth. - Tala Eagling-Vose; Barnaby Martin; Daniël Paulusma; Mark H. Siggers; Siani Smith (CoRR, 2024)

Model-checking positive equality free logic on a fixed structure (direttissima). - Manuel Bodirsky; Marcin Kozik; Florent R. Madelaine; Barnaby Martin; Michal Wrona (CoRR, 2024)

The Riis Complexity Gap for QBF Resolution. - Olaf Beyersdorff; Judith Clymo; Stefan S. Dantchev; Barnaby Martin (J. Satisf. Boolean Model. Comput., 2024)

Complexity Classification Transfer for CSPs via Algebraic Products. - Manuel Bodirsky; Peter Jonsson; Barnaby Martin; Antoine Mottet; Zaneta Semanisinová (SIAM J. Comput., 2024)

Proof Complexity and the Binary Encoding of Combinatorial Principles. - Stefan S. Dantchev; Nicola Galesi; Abdul Ghani 001; Barnaby Martin (SIAM J. Comput., 2024)

Restricted CSPs and F-Free Digraph Algorithmics. - Santiago Guzmán-Pro; Barnaby Martin (ICALP, 2025)

Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. - Hans L. Bodlaender; Matthew Johnson 002; Barnaby Martin; Jelle J. Oostveen; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (J. Comput. Syst. Sci., 2025)

Acyclic, star and injective colouring: A complexity picture for H-free graphs. - Jan Bok; Nikola Jedlicková; Barnaby Martin; Pascal Ochem; Daniël Paulusma; Siani Smith (J. Comput. Syst. Sci., 2025)

A forbidden subgraph study for cut problems on graphs permitting loops and multiedges. - Tala Eagling-Vose; Barnaby Martin; Daniël Paulusma; Siani Smith (CoRR, 2025)

Complexity Framework for Forbidden Subgraphs I: The Framework. - Matthew Johnson 002; Barnaby Martin; Jelle J. Oostveen; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen (Algorithmica, 2025)