Arrow Research search

Author name cluster

Barnaby Martin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

MFCS Conference 2023 Conference Paper

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

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

For any finite set ℋ = {H_1, …, H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1, …, H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

Details

TCS Journal 2023 Journal Article

Few induced disjoint paths for H-free graphs

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

Paths P 1, …, P k in a graph G = ( V, E ) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k -Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices ( s i, t i ) contains k mutually induced paths P i such that each P i starts from s i and ends at t i. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-Induced Disjoint Paths is NP-complete. We prove new complexity results for k -Induced Disjoint Paths if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where k is part of the input.

Details DOI

SODA Conference 2023 Conference Paper

The complete classification for quantified equality constraints

  • Dmitriy Zhuk
  • Barnaby Martin
  • Michal Wrona

We prove that QCSP(ℕ; x = y → y = z ) is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP over equality languages as a trichotomy between Logspace, NP-complete and PSpace-complete. We additionally settle the classification for bounded alternation QCSP(Γ), for Γ an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.

Details

TCS Journal 2022 Journal Article

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

  • Barnaby Martin
  • Daniël Paulusma
  • Siani Smith

For a fixed integer, the k -Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that for all k ≥ 3, the k -Colouring problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Details DOI

TCS Journal 2022 Journal Article

Disjoint paths and connected subgraphs for H-free graphs

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

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k -Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k -Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths. Moreover, we give exact algorithms for Disjoint Paths and Disjoint Connected Subgraphs on graphs with n vertices and m edges that have running times of O ( 2 n n 2 k ) and O ( 3 n k m ), respectively.

Details DOI

TCS Journal 2022 Journal Article

Partitioning H-free graphs of bounded diameter

  • Christoph Brause
  • Petr Golovach
  • Barnaby Martin
  • Daniël Paulusma
  • Siani Smith

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph H contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study (MFCS 2019) on the k -Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the H-free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to H-free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.

Details DOI

STOC Conference 2020 Conference Paper

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 finite language over 3 elements which contains all constants. In particular, such problems are either in P, NP-complete, co-NP-complete or PSpace-complete. Our classification refutes the hitherto widely-believed Chen Conjecture.

Details

MFCS Conference 2019 Conference Paper

Colouring H-Free Graphs of Bounded Diameter

  • Barnaby Martin
  • Daniël Paulusma
  • Siani Smith

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k >= 3. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Details

IJCAI Conference 2018 Conference Paper

Classification Transfer for Qualitative Reasoning Problems

  • Manuel Bodirsky
  • Peter Jonsson
  • Barnaby Martin
  • Antoine Mottet

We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pp-homotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen's Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.

PDF Details

MFCS Conference 2018 Conference Paper

Consistency for Counting Quantifiers

  • Florent R. Madelaine
  • Barnaby Martin

We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard.

Details

TCS Journal 2017 Journal Article

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic

  • Christian Glaßer
  • Peter Jonsson
  • Barnaby Martin

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [1] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits—involving complement, intersection, union and multiplication—to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [1] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, ( N; × ), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

Details DOI

TCS Journal 2017 Journal Article

The complexity of counting quantifiers on equality languages

  • Barnaby Martin
  • András Pongrácz
  • Michał Wrona

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 existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.

Details DOI

MFCS Conference 2017 Conference Paper

The Complexity of Quantified Constraints Using the Algebraic Formulation

  • Catarina Carvalho
  • Barnaby Martin
  • Dmitriy Zhuk

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove a converse, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying the moral correctness of what we term the Chen Conjecture. We examine in closer detail the situation for domains of size three. Over any finite domain, the only type of PGP that can occur is switchability. Switchability was introduced by Chen as a generalisation of the already-known Collapsibility. For three-element domain algebras A that are Switchable, we prove that for every finite subset Delta of Inv(A), Pol(Delta) is Collapsible. The significance of this is that, for QCSP on finite structures (over three-element domain), all QCSP tractability explained by Switchability is already explained by Collapsibility. Finally, we present a three-element domain complexity classification vignette, using known as well as derived results.

Details

I&C Journal 2016 Journal Article

Distance constraint satisfaction problems

  • Manuel Bodirsky
  • Victor Dalmau
  • Barnaby Martin
  • Antoine Mottet
  • Michael Pinsker

We study the complexity of constraint satisfaction problems for templates Γ over the integers where the relations are first-order definable from the successor function. In the case that Γ is locally finite (i. e. , the Gaifman graph of Γ has finite degree), we show that Γ is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for Γ can be solved in polynomial time, or Γ is homomorphically equivalent to a finite transitive structure, or the CSP for Γ is NP-complete. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.

Details DOI

CSL Conference 2015 Conference Paper

First-Order Queries on Finite Abelian Groups

  • Simone Bova
  • Barnaby Martin

We study the computational problem of checking whether a logical sentence is true in a finite abelian group. We prove that model checking first-order sentences on finite abelian groups is fixed-parameter tractable, when parameterized by the size of the sentence. We also prove that model checking monadic second-order sentences on finite abelian groups finitely presented by integer matrices is not fixed-parameter tractable (under standard assumptions in parameterized complexity).

Details

MFCS Conference 2010 Conference Paper

Distance Constraint Satisfaction Problems

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

Abstract We study the complexity of constraint satisfaction problems for templates \(\it\Gamma\) that are first-order definable in \(({\mathbb Z}; {\it suc})\), the integers with the successor relation. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), we provide a full classification for the case that \(\it\Gamma\) is locally finite (i. e. , the Gaifman graph of \(\it\Gamma\) has finite degree). We show that one of the following is true: The structure \(\it\Gamma\) is homomorphically equivalent to a structure with a certain majority polymorphism (which we call modular median ) and CSP \((\it\Gamma)\) can be solved in polynomial time, or \(\it\Gamma\) is homomorphically equivalent to a finite transitive structure, or CSP \((\it\Gamma)\) is NP-complete.

Details

CSL Conference 2010 Conference Paper

The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case

  • Barnaby Martin
  • Jos Martin

Abstract We study the complexity of evaluating positive equality-free sentences of first-order logic over fixed, finite structures \(\mathcal{B}\). This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP \((\mathcal{B})\). Extending the algebraic methods of a previous paper, we derive a complete complexity classification for these problems as \(\mathcal{B}\) ranges over structures of domain size 4. Specifically, each problem is either in L, is NP -complete, is co-NP -complete or is Pspace -complete.

Details

TCS Journal 2009 Journal Article

Tight rank lower bounds for the Sherali–Adams proof system

  • Stefan Dantchev
  • Barnaby Martin
  • Mark Rhodes

We consider a proof (more accurately, refutation) system based on the Sherali–Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s, then we prove that the SA rank of F is ≤ k and the SA size of F is ≤ ( k + 1 ) s + 1. We establish that the SA rank of both the Pigeonhole Principle PHP n − 1 n and the Least Number Principle LNP n is n − 2. Since the SA refutation system rank-simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS.

Details DOI

FOCS Conference 2007 Conference Paper

Parameterized Proof Complexity

  • Stefan S. Dantchev
  • Barnaby Martin
  • Stefan Szeider

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional CNF formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W(M. Cesati, 2006) by showing that there is no fpt-bounded parameterized proof system, i. e. , that there is no proof system that admits proofs of size f(k)n O(1) where f is a computable function and n represents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution, and show that this system is not fpt-bounded. Indeed we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of size n. We establish a dichotomy theorem that splits the exponential case of Riis's complexity-gap Theorem into two sub-cases, one that admits proofs of size f(k)n O(1) and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2 k n 2. This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the "non-FPT" category of our dichotomy.

Details
v2026.09.13