Staff profile

I am an Associate Professor at Durham University in the Algorithms and Complexity Group (ACiD) within the Department of Computer Science. I was previously a lecturer in the Foundations of Computing Group at Middlesex University. Before my permanent appointments I undertook a number of post-doctoral positions in Durham and Paris.

My interests include Complexity Theory in general (Proof Complexity as well as Computational Complexity); Finite Model Theory; and the links between logic and complexity. I am mostly working now on forms of Constraint Satisfaction Problem, Proof Complexity and Algorithmic Graph Theory.

Conference Paper

• Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs
  
  Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024) (pp. 47:1-47:18). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.ISAAC.2024.47
• Complexity framework for forbidden subgraphs IV: The Steiner Forest problem
  
  Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Lecture Notes in Computer Science, 14764, 206-217. https://doi.org/10.1007/978-3-031-63021-7_16
• Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs
  
  Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) (pp. 29:1-29:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SWAT.2024.29
• Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
  
  Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (pp. 57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (pp. 398-411). Springer Verlag. https://doi.org/10.1007/978-3-031-15914-5_29
• The Complexity of L(p,q)-Edge-Labelling
  
  Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (pp. 175-186). Springer Verlag. https://doi.org/10.1007/978-3-030-96731-4_15
• Few induced disjoint paths for H-free graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (pp. 89-101). Springer. https://doi.org/10.1007/978-3-031-18530-4_7
• Injective colouring for H-free graphs
  
  Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs. In Lecture Notes in Computer Science. Springer Verlag.
• Acyclic, star and injective colouring: bounding the diameter
  
  Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Łukasz Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (1st ed., pp. 336-348). Springer Verlag. https://doi.org/10.1007/978-3-030-86838-3_26
• QCSP on reflexive tournaments
  
  Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), Leibniz International Proceedings in Informatics (pp. 58:1-58:15). Dagstuhl. https://doi.org/10.4230/lipics.esa.2021.58
• Disjoint paths and connected subgraphs for H-free graphs
  
  Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (pp. 414-427). Springer Verlag. https://doi.org/10.1007/978-3-030-79987-8_29
• Partitioning H-free graphs of bounded diameter
  
  Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn & K. Sadakane (Eds.), Leibniz International Proceedings in Informatics (pp. 21:1-21:14). Schloss Dagstuhl. https://doi.org/10.4230/lipics.isaac.2021.21
• Colouring graphs of bounded diameter in the absence of small cycles
  
  Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri & F. Corò (Eds.), Lecture Notes in Computer Science (pp. 367-380). Springer Verlag. https://doi.org/10.1007/978-3-030-75242-2_26
• Acyclic, star and injective colouring: a complexity picture for H-free graphs
  
  Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. In Leibniz International Proceedings in Informatics. Schloss Dagstuhl. https://doi.org/10.4230/lipics.esa.2020.22
• QCSP monsters and the demise of the chen conjecture
  
  Zhuk, D., & Martin, B. (2020). QCSP monsters and the demise of the chen conjecture. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 91-104). Association for Computing Machinery (ACM). https://doi.org/10.1145/3357713.3384232
• Sherali-Adams and the binary encoding of combinatorial principles
  
  Dantchev, S., Ghani, A., & Martin, B. (2020). Sherali-Adams and the binary encoding of combinatorial principles. In Y. Kohayakawa & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (pp. 336-347). Springer Verlag. https://doi.org/10.1007/978-3-030-61792-9_27
• Colouring H-free graphs of bounded diameter
  
  Martin, B., Paulusma, D., & Smith, S. (2019). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). (pp. 14:1-14:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2019.14
• Resolution and the binary encoding of combinatorial principles
  
  Dantchev, S., Galesi, N., & Martin, B. (2019). Resolution and the binary encoding of combinatorial principles. In A. Shpilka (Ed.), 34th Computational Complexity Conference (CCC 2019). (pp. 6:1-6:25). Dagstuhl Publishing. https://doi.org/10.4230/lipics.ccc.2019.6
• Consistency for counting quantifiers
  
  Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). (pp. 11:1-11:13). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing. https://doi.org/10.4230/lipics.mfcs.2018.11
• The complexity of disjunctive linear Diophantine constraints
  
  Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018). The complexity of disjunctive linear Diophantine constraints. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). (pp. 33:1-33:16). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing. https://doi.org/10.4230/lipics.mfcs.2018.33
• Classification Transfer for Qualitative Reasoning Problems
  
  Bodirsky, M., Jonsson, P., Martin, B., & Mottet, A. (2018). Classification Transfer for Qualitative Reasoning Problems. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18). (pp. 1256-1262). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2018/175
• Surjective H-Colouring over Reflexive Digraphs
  
  Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France. (pp. 49:1-49:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.stacs.2018.49
• Disconnected Cuts in Claw-free Graphs
  
  Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018). (pp. 61:1-61:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing. https://doi.org/10.4230/lipics.esa.2018.61
• The complexity of quantified constraints using the algebraic formulation
  
  Carvalho, C., Martin, B., Zhuk, D., Larsen, K. G., Bodlaender, H. L., & Raskin, J. (2017). The complexity of quantified constraints using the algebraic formulation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.27
• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
  
  Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016.. Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2016.119
• From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
  
  Carvalho, C., Madelaine, F. R., & Martin, B. (2015). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. In Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) : 6-10 July 2015, Kyoto, Japan. (pp. 462-474). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/lics.2015.50
• Constraint Satisfaction Problems over the Integers with Successor
  
  Bodirsky, M., Martin, B., & Mottet, A. (2015). Constraint Satisfaction Problems over the Integers with Successor. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Proceedings. Part I. (pp. 256-267). Springer Verlag. https://doi.org/10.1007/978-3-662-47672-7_21

Journal Article

• Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
  
  Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. Journal of Computer and System Sciences, 154, Article 103682. https://doi.org/10.1016/j.jcss.2025.103682
• Acyclic, star and injective colouring: A complexity picture for H-free graphs
  
  Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662
• Complexity Framework for Forbidden Subgraphs I: The Framework
  
  Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2
• Complexity Classification Transfer for CSPs via Algebraic Products
  
  Bodirsky, M., Jonsson, P., Martin, B., Mottet, A., & Semanišinová, Žaneta. (2024). Complexity Classification Transfer for CSPs via Algebraic Products. SIAM Journal on Computing, 53(5), 1293-1353. https://doi.org/10.1137/22m1534304
• Proof Complexity and the Binary Encoding of Combinatorial Principles
  
  Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Proof Complexity and the Binary Encoding of Combinatorial Principles. SIAM Journal on Computing, 53(3), 764-802. https://doi.org/10.1137/20m134784x
• Depth lower bounds in Stabbing Planes for combinatorial principles
  
  Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Depth lower bounds in Stabbing Planes for combinatorial principles. Logical Methods in Computer Science, 20(1), 1-19. https://doi.org/10.46298/lmcs-20%281%3A1%292024
• The Riis Complexity Gap for QBF Resolution
  
  Beyersdorff, O., Clymo, J., Dantchev, S., & Martin, B. (2024). The Riis Complexity Gap for QBF Resolution. Journal on Satisfiability, Boolean Modeling and Computation, 15(1), 9-25. https://doi.org/10.3233/sat-231505
• The Complexity of L(p, q)-Edge-Labelling
  
  Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4
• Few induced disjoint paths for H-free graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z
• The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
  
  Carvalho, C., Madelaine, F., Martin, B., & Zhuk, D. (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic, 24(1), Article 5. https://doi.org/10.1145/3568397
• QCSP Monsters and the Demise of the Chen Conjecture
  
  Zhuk, D., & Martin, B. (2022). QCSP Monsters and the Demise of the Chen Conjecture. Journal of the ACM, 69(5), Article 35. https://doi.org/10.1145/3563820
• Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter
  
  Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034
• Partitioning H-free graphs of bounded diameter
  
  Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009
• QCSP on reflexive tournaments
  
  Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), Article 14. https://doi.org/10.1145/3508069
• Colouring graphs of bounded diameter in the absence of small cycles
  
  Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026
• Hard problems that quickly become very easy
  
  Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174. https://doi.org/10.1016/j.ipl.2021.106213
• The lattice and semigroup structure of multipermutations
  
  Carvalho, C., & Martin, B. (2022). The lattice and semigroup structure of multipermutations. International Journal of Algebra and Computation, 32(2), 211-235. https://doi.org/10.1142/s0218196722500096
• Disjoint paths and connected subgraphs for H-free graphs
  
  Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019
• Acyclic, Star, and Injective Colouring: Bounding the diameter
  
  Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2). https://doi.org/10.37236/10738
• Disconnected cuts in claw-free graphs
  
  Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005
• Constraint satisfaction problems for reducts of homogeneous graphs
  
  Bodirsky, M., Martin, B., Pinsker, M., & Pongracz, A. (2019). Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4), 1224-1264. https://doi.org/10.1137/16m1082974
• Surjective H-colouring: New hardness results
  
  Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084
• Surjective H-Colouring over reflexive digraphs
  
  Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431
• On the Complexity of the Model Checking Problem
  
  Madelaine, F. R., & Martin, B. D. (2018). On the Complexity of the Model Checking Problem. SIAM Journal on Computing, 47(3), 769-797. https://doi.org/10.1137/140965715
• Discrete Temporal Constraint Satisfaction Problems
  
  Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the Association for Computing Machinery., 65(2), Article 9. https://doi.org/10.1145/3154832
• Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic
  
  Glaßer, C., Jonsson, P., & Martin, B. (2017). Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science, 703, 18-36. https://doi.org/10.1016/j.tcs.2017.08.025
• The packing chromatic number of the infinite square lattice is between 13 and 15
  
  Martin, B., Raimondi, F., Chen, T., & Martin, J. (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225, 136-142. https://doi.org/10.1016/j.dam.2017.03.013
• Quantified Constraint Satisfaction Problem on semicomplete digraphs
  
  Đ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
• The complexity of counting quantifiers on equality languages
  
  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
• The computational complexity of disconnected cut and 2K2-partition
  
  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
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
  
  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
• Parameterized Proof Complexity
  
  Dantchev, S., Martin, B., & Szeider, S. (2011). Parameterized Proof Complexity. Computational Complexity, 20(1), 51-85. https://doi.org/10.1007/s00037-010-0001-1