All Outputs (50)

Depth lower bounds in Stabbing Planes for combinatorial principles (2024)
Journal Article
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

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 inequalities instead of single variables. The techniques known so far to prov... Read More about Depth lower bounds in Stabbing Planes for combinatorial principles.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Presentation / Conference Contribution
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) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4

The L(p, q)-EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p, q)-Edge-Labelling.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
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

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Few induced disjoint paths for H-free graphs (2022)
Presentation / Conference Contribution
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 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7

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... Read More about Few induced disjoint paths for H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Journal Article
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

Paths in a graph are mutually induced if any two distinct and 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 contains k mutu... Read More about Few induced disjoint paths for H-free graphs.

The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation (2022)
Journal Article
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

Let A be an idempotent algebra on a finite domain. By mediating between results of Chen [1] and Zhuk [2], we argue that if A satisfies the polynomially generated powers property (PGP) and B is a constraint language invariant under A (that is, in Inv(... Read More about The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2022)
Presentation / Conference Contribution
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 (398-411). https://doi.org/10.1007/978-3-031-15914-5_29

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter (2022)
Journal Article
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

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 ind... Read More about Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.

Partitioning H-free graphs of bounded diameter (2022)
Journal Article
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

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 ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, Star, and Injective Colouring: Bounding the diameter (2022)
Journal Article
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

We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices... Read More about Acyclic, Star, and Injective Colouring: Bounding the diameter.

QCSP on reflexive tournaments (2022)
Journal Article
Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069

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 into a sequence of strongly connected components H1,…,Hn so that ther... Read More about QCSP on reflexive tournaments.

Colouring graphs of bounded diameter in the absence of small cycles (2022)
Journal Article
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

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H-f... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

The Complexity of L(p,q)-Edge-Labelling (2022)
Presentation / Conference Contribution
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 (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Partitioning H-free graphs of bounded diameter (2021)
Presentation / Conference Contribution
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.), . https://doi.org/10.4230/lipics.isaac.2021.21

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 ide... Read More about Partitioning H-free graphs of bounded diameter.

The lattice and semigroup structure of multipermutations (2021)
Journal Article
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

We study the algebraic properties of binary relations whose underlying digraph is smooth, that is, has no source or sink. Such objects have been studied as surjective hyper-operations (shops) on the corresponding vertex set, and as binary relations t... Read More about The lattice and semigroup structure of multipermutations.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Journal Article
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

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 Dis... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Hard problems that quickly become very easy (2021)
Journal Article
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

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 for every hereditary graph class that is not equal to the class of all g... Read More about Hard problems that quickly become very easy.

Acyclic, star and injective colouring: bounding the diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. 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 (336-348). https://doi.org/10.1007/978-3-030-86838-3_26

We examine the effect of bounding the diameter for wellstudied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively.... Read More about Acyclic, star and injective colouring: bounding the diameter.

QCSP on reflexive tournaments (2021)
Presentation / Conference Contribution
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.), . https://doi.org/10.4230/lipics.esa.2021.58

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 into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.