Barnaby Martin

According to our database, Barnaby Martin authored at least 97 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Graph Homomorphism, Monotone Classes and Bounded Pathwidth.

Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Mark Siggers, Siani Smith

CoRR, 2024

2023

The Complexity of L(p, q)-Edge-Labelling.

Gaétan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith

Algorithmica, November, 2023

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Algorithmica, September, 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., January, 2023

Few induced disjoint paths for <i>H</i>-free graphs.

Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Theor. Comput. Sci., 2023

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.

Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

CoRR, 2023

The complete classification for quantified equality constraints.

Dmitriy Zhuk, Barnaby Martin, Michal Wrona

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs.

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

QCSP on Reflexive Tournaments.

Benoît Larose, Barnaby Martin, Petar Markovic, Daniël Paulusma, Siani Smith, Stanislav Zivný

ACM Trans. Comput. Log., 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

Disjoint paths and connected subgraphs for <i>H</i>-free graphs.

Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Theor. Comput. Sci., 2022

Partitioning <i>H</i>-free graphs of bounded diameter.

Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith

Theor. Comput. Sci., 2022

QCSP Monsters and the Demise of the Chen Conjecture.

Dmitriy Zhuk, Barnaby Martin

J. ACM, 2022

Hard problems that quickly become very easy.

Barnaby Martin, Daniël Paulusma, Siani Smith

Inf. Process. Lett., 2022

The lattice and semigroup structure of multipermutations.

Catarina Carvalho, Barnaby Martin

Int. J. Algebra Comput., 2022

Colouring graphs of bounded diameter in the absence of small cycles.

Barnaby Martin, Daniël Paulusma, Siani Smith

Discret. Appl. Math., 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

Complexity Framework For Forbidden Subgraphs.

Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

CoRR, 2022

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs.

Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen

CoRR, 2022

Complexity Classification Transfer for CSPs via Algebraic Products.

Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová

CoRR, 2022

When bounds consistency implies domain consistency for regular counting constraints.

Barnaby Martin, Justin Pearson

Constraints An Int. J., 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

Few Induced Disjoint Paths for H-Free Graphs.

Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the Combinatorial Optimization - 7th International Symposium, 2022

2021

Depth lower bounds in Stabbing Planes for combinatorial principles.

Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

Electron. Colloquium Comput. Complex., 2021

The complete classification for quantified equality constraints.

Dmitriy Zhuk, Barnaby Martin

CoRR, 2021

Acyclic, Star, and Injective Colouring: Bounding the Diameter.

Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the Combinatorial Algorithms - 32nd International Workshop, 2021

Partitioning H-Free Graphs of Bounded Diameter.

Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Injective Colouring for H-Free Graphs.

Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith

Proceedings of the Computer Science - Theory and Applications, 2021

2020

Disconnected cuts in claw-free graphs.

Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen

J. Comput. Syst. Sci., 2020

Proof complexity and the binary encoding of combinatorial principles.

Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

CoRR, 2020

Sherali-Adams and the Binary Encoding of Combinatorial Principles.

Stefan S. Dantchev, Abdul Ghani, Barnaby Martin

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs.

Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Surjective H-Colouring over Reflexive Digraphs.

Benoît Larose, Barnaby Martin, Daniël Paulusma

ACM Trans. Comput. Theory, 2019

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz

SIAM J. Comput., 2019

Report on BCTCS & AlgoUK 2019.

Matthew Johnson, Barnaby Martin, George B. Mertzios, Daniël Paulusma

Bull. EATCS, 2019

Surjective H-colouring: New hardness results.

Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart

Comput., 2019

Colouring H-Free Graphs of Bounded Diameter.

Barnaby Martin, Daniël Paulusma, Siani Smith

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

On the Complexity of the Model Checking Problem.

Florent R. Madelaine, Barnaby Martin

SIAM J. Comput., 2018

Discrete Temporal Constraint Satisfaction Problems.

Manuel Bodirsky, Barnaby Martin, Antoine Mottet

J. ACM, 2018

Resolution and the binary encoding of combinatorial principles.

Stefan S. Dantchev, Nicola Galesi, Barnaby Martin

Electron. Colloquium Comput. Complex., 2018

The Riis Complexity Gap for QBF Resolution.

Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin

Electron. Colloquium Comput. Complex., 2018

Consistency for Counting Quantifiers.

Florent R. Madelaine, Barnaby Martin

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

The Complexity of Disjunctive Linear Diophantine Constraints.

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Classification Transfer for Qualitative Reasoning Problems.

Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

2017

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs.

Petar Dapic, Petar Markovic, Barnaby Martin

ACM Trans. Comput. Log., 2017

The complexity of counting quantifiers on equality languages.

Barnaby Martin, András Pongrácz, Michal Wrona

Theor. Comput. Sci., 2017

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic.

Christian Glaßer, Peter Jonsson, Barnaby Martin

Theor. Comput. Sci., 2017

The packing chromatic number of the infinite square lattice is between 13 and 15.

Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin

Discret. Appl. Math., 2017

The complexity of quantified constraints.

Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

CoRR, 2017

The Complexity of Quantified Constraints Using the Algebraic Formulation.

Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Quantified Constraints in Twenty Seventeen.

Barnaby Martin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Distance constraint satisfaction problems.

Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Antoine Mottet, Michael Pinsker

Inf. Comput., 2016

Report on BCTCS 2015.

Barnaby Martin

Bull. EATCS, 2016

On the Chen Conjecture regarding the complexity of QCSPs.

Barnaby Martin

CoRR, 2016

2015

Constraint Satisfaction with Counting Quantifiers.

Barnaby Martin, Florent R. Madelaine, Juraj Stacho

SIAM J. Discret. Math., 2015

The computational complexity of disconnected cut and 2_K2-partition.

Barnaby Martin, Daniël Paulusma

J. Comb. Theory, Ser. B, 2015

Switchability and collapsibility of Gap Algebras.

Barnaby Martin, Dmitriy Zhuk

CoRR, 2015

The packing chromatic number of the infinite square lattice is less than or equal to 16.

Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin

CoRR, 2015

Constraint Satisfaction Problems around Skolem Arithmetic.

Christian Glaßer, Peter Jonsson, Barnaby Martin

CoRR, 2015

Quantified Constraints and Containment Problems.

Hubie Chen, Florent R. Madelaine, Barnaby Martin

Log. Methods Comput. Sci., 2015

From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP.

Catarina Carvalho, Florent R. Madelaine, Barnaby Martin

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Constraint Satisfaction Problems over the Integers with Successor.

Manuel Bodirsky, Barnaby Martin, Antoine Mottet

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

First-Order Queries on Finite Abelian Groups.

Simone Bova, Barnaby Martin

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

2014

Relativization makes contradictions harder for Resolution.

Stefan S. Dantchev, Barnaby Martin

Ann. Pure Appl. Log., 2014

QCSP on Semicomplete Digraphs.

Petar Dapic, Petar Markovic, Barnaby Martin

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Constraint Satisfaction with Counting Quantifiers 2.

Barnaby Martin, Juraj Stacho

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Relativisation makes contradictions harder for Resolution

Stefan S. Dantchev, Barnaby Martin

CoRR, 2013

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems.

Stefan S. Dantchev, Barnaby Martin

Comput. Complex., 2013

QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability.

Florent R. Madelaine, Barnaby Martin

Proceedings of the Computer Science - Theory and Applications, 2013

Parameterized Resolution with Bounded Conjunction.

Stefan S. Dantchev, Barnaby Martin

Proceedings of the Computer Science - Theory and Applications, 2013

2012

The Complexity of Positive First-Order Logic without Equality.

Florent R. Madelaine, Barnaby Martin

ACM Trans. Comput. Log., 2012

Cutting Planes and the Parameter Cutwidth.

Stefan S. Dantchev, Barnaby Martin

Theory Comput. Syst., 2012

The complexity of surjective homomorphism problems - a survey.

Manuel Bodirsky, Jan Kára, Barnaby Martin

Discret. Appl. Math., 2012

Parameterized Proof Complexity and W[1]

Barnaby Martin

CoRR, 2012

The limits of tractability in Resolution-based propositional proof systems.

Stefan S. Dantchev, Barnaby Martin

Ann. Pure Appl. Log., 2012

Finding vertex-surjective graph homomorphisms.

Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma

Acta Informatica, 2012

Containment, Equivalence and Coreness from CSP to QCSP and Beyond.

Florent R. Madelaine, Barnaby Martin

Proceedings of the Principles and Practice of Constraint Programming, 2012

2011

Low-level dichotomy for quantified constraint satisfaction problems.

Barnaby Martin

Inf. Process. Lett., 2011

The Computational Complexity of Disconnected Cut and 2K2-Partition

Barnaby Martin, Daniël Paulusma

CoRR, 2011

Parameterized Proof Complexity.

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

Comput. Complex., 2011

A Tetrachotomy for Positive First-Order Logic without Equality.

Florent R. Madelaine, Barnaby Martin

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

The Computational Complexity of Disconnected Cut and 2K 2-Partition.

Barnaby Martin, Daniël Paulusma

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

QCSP on Partially Reflexive Forests.

Barnaby Martin

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

2010

Distance Constraint Satisfaction Problems.

Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

The Lattice Structure of Sets of Surjective Hyper-Operations.

Barnaby Martin

Proceedings of the Principles and Practice of Constraint Programming - CP 2010, 2010

2009

Tight rank lower bounds for the Sherali-Adams proof system.

Stefan S. Dantchev, Barnaby Martin, Mark Nicholas Charles Rhodes

Theor. Comput. Sci., 2009

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

Manuel Bodirsky, Martin Hils, Barnaby Martin

Log. Methods Comput. Sci., 2009

The complexity of positive first-order logic without equality II: The four-element case.

Barnaby Martin, Jos Martin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

2008

Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three

Barnaby Martin

CoRR, 2008

First-Order Model Checking Problems Parameterized by the Model.

Barnaby Martin

Proceedings of the Logic and Theory of Algorithms, 2008

2007

Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution.

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

Electron. Colloquium Comput. Complex., 2007

On the Complexity of a Derivative Chess Problem

Barnaby Martin

CoRR, 2007

Hierarchies in Fragments of Monadic Strict NP.

Barnaby Martin, Florent R. Madelaine

Proceedings of the Computation and Logic in the Real World, 2007

2006

Dichotomies and Duality in First-order Model Checking Problems

Barnaby Martin

CoRR, 2006

Towards a Trichotomy for Quantified <i>H</i>-Coloring.

Barnaby Martin, Florent R. Madelaine

Proceedings of the Logical Approaches to Computational Barriers, 2006

2005

Logic, computation and constraint satisfaction.

Barnaby Martin

PhD thesis, 2005