Source author record

Nick Brettell

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cyclic matroids

For all positive integers $s$ and $t$ exceeding one, a matroid $M$ on $n$ elements is {\em nearly $(s, t)$ -cyclic} if there is a cyclic ordering $σ$ of its ground set such that every $s-1$ consecutive elements of $σ$ are contained in an $s$ -element circuit and every $t-1$ consecutive elements of $σ$ are contained in a $t$ -element cocircuit. In the case $s=t$ , nearly $(s, s)$ -cyclic matroids have been studied previously. In this paper, we show that if $M$ is nearly $(s, t)$ -cyclic and $n$ is sufficiently large, then these $s$ -element circuits and $t$ -element cocircuits are consecutive in $σ$ in a prescribed way, that is, $M$ is " $(s, t)$ -cyclic". Furthermore, we show that, given $s$ and $t$ where $t\ge s$ , every $(s, t)$ -cyclic matroid on $n > s+t-2$ elements is a weak-map image of the $\left(\frac{t-s}{2}\right)$ -th truncation of a certain $(s, s)$ -cyclic matroid. If $s=3$ , this certain matroid is the rank- $\frac{n}{2}$ whirl, and if $s=4$ , this certain matroid is the rank- $\frac{n}{2}$ free swirl.

preprint2021arXiv

$N$ -detachable pairs in 3-connected matroids III: the theorem

Let $M$ be a 3-connected matroid, and let $N$ be a 3-connected minor of $M$ . A pair $\{x_1,x_2\} \subseteq E(M)$ is $N$ -detachable if one of the matroids $M/x_1/x_2$ or $M \backslash x_1 \backslash x_2$ is both 3-connected and has an $N$ -minor. This is the third and final paper in a series where we prove that if $|E(M)|-|E(N)| \ge 10$ , then either $M$ has an $N$ -detachable pair after possibly performing a single $Δ$ - $Y$ or $Y$ - $Δ$ exchange, or $M$ is essentially $N$ with a spike attached. Moreover, we describe the additional structures that arise if we require only that $|E(M)|-|E(N)| \ge 5$ .

preprint2020arXiv

$N$ -detachable pairs in 3-connected matroids I: unveiling $X$

Let $M$ be a 3-connected matroid, and let $N$ be a 3-connected minor of $M$ . We say that a pair $\{x_1,x_2\} \subseteq E(M)$ is $N$ -detachable if one of the matroids $M/x_1/x_2$ or $M \backslash x_1 \backslash x_2$ is both 3-connected and has an $N$ -minor. This is the first in a series of three papers where we describe the structures that arise when it is not possible to find an $N$ -detachable pair in $M$ . In this paper, we prove that if $M$ has no $N$ -detachable pairs, then either $M$ has a 3-separating set, which we call $X$ , with certain strong structural properties, or $M$ has one of three particular 3-separators that can appear in a matroid with no $N$ -detachable pairs.

preprint2020arXiv

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$ , for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$ , where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$ -time algorithm for Even Cycle Transversal under the ETH.

preprint2020arXiv

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective

We prove that the class of $(K_t,sP_1+P_5)$ -free graphs has bounded mim-width for every $s\geq 0$ and $t\geq 1$ , and that there is a polynomial-time algorithm that, given a graph in the class, computes a branch decomposition of constant mim-width. A large number of \NP-complete graph problems become polynomial-time solvable on graph classes with bounded mim-width and for which a branch decomposition is quickly computable. The $k$ -Colouring problem is an example of such a problem. For this problem, we may assume that the input graph is $K_{k+1}$ -free. Then, as a consequence of our result, we obtain a new proof for the known result that for every fixed $k\geq 1$ and $s\geq 0$ , $k$ -Colouring is polynomial-time solvable for $(sP_1+P_5)$ -free graphs. In fact, our findings show that the underlying reason for this polynomial-time algorithm is that the class has bounded mim-width.

preprint2018arXiv

Excluded minors are almost fragile

Let $M$ be an excluded minor for the class of $\mathbb{P}$ -representable matroids for some partial field $\mathbb P$ , and let $N$ be a $3$ -connected strong $\mathbb{P}$ -stabilizer that is non-binary. We prove that either $M$ is bounded relative to $N$ , or, up to replacing $M$ by a $Δ$ - $Y$ -equivalent excluded minor, we can choose a pair of elements $\{a,b\}$ such that either $M\backslash \{a,b\}$ is $N$ -fragile, or $M^* \backslash \{a,b\}$ is $N^*$ -fragile.

preprint2018arXiv

On a generalisation of spikes

We consider matroids with the property that every subset of the ground set of size $t$ is contained in both an $\ell$ -element circuit and an $\ell$ -element cocircuit; we say that such a matroid has the $(t,\ell)$ -property. We show that for any positive integer $t$ , there is a finite number of matroids with the $(t,\ell)$ -property for $\ell<2t$ ; however, matroids with the $(t,2t)$ -property form an infinite family. We say a matroid is a $t$ -spike if there is a partition of the ground set into pairs such that the union of any $t$ pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the $(t,2t)$ -property, then it is a $t$ -spike. Finally, we present some properties of $t$ -spikes.

preprint2016arXiv

Colouring graphs with constraints on connectivity

A graph $G$ has maximal local edge-connectivity $k$ if the maximum number of edge-disjoint paths between every pair of distinct vertices $x$ and $y$ is at most $k$ . We prove Brooks-type theorems for $k$ -connected graphs with maximal local edge-connectivity $k$ , and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph $G$ with maximal local connectivity 3, outputs an optimal colouring for $G$ . On the other hand, we prove, for $k \ge 3$ , that $k$ -colourability is NP-complete when restricted to minimally $k$ -connected graphs, and 3-colourability is NP-complete when restricted to $(k-1)$ -connected graphs with maximal local connectivity $k$ . Finally, we consider a parameterization of $k$ -colourability based on the number of vertices of degree at least $k+1$ , and prove that, even when $k$ is part of the input, the corresponding parameterized problem is FPT.

preprint2016arXiv

Parameterized vertex deletion problems for hereditary graph classes with a block property

For a class of graphs $\mathcal{P}$ , the Bounded $\mathcal{P}$ -Block Vertex Deletion problem asks, given a graph $G$ on $n$ vertices and positive integers $k$ and $d$ , whether there is a set $S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $\mathcal{P}$ . We show that when $\mathcal{P}$ satisfies a natural hereditary property and is recognizable in polynomial time, Bounded $\mathcal{P}$ -Block Vertex Deletion can be solved in time $2^{O(k \log d)}n^{O(1)}$ . When $\mathcal{P}$ contains all split graphs, we show that this running time is essentially optimal unless the Exponential Time Hypothesis fails. On the other hand, if $\mathcal{P}$ consists of only complete graphs, or only cycle graphs and $K_2$ , then Bounded $\mathcal{P}$ -Block Vertex Deletion admits a $c^{k}n^{O(1)}$ -time algorithm for some constant $c$ independent of $d$ . We also show that Bounded $\mathcal{P}$ -Block Vertex Deletion admits a kernel with $O(k^2 d^7)$ vertices.

preprint2015arXiv

Orienting edges to fight fire in graphs

We investigate a new oriented variant of the Firefighter Problem. In the traditional Firefighter Problem, a fire breaks out at a given vertex of a graph, and at each time interval spreads to neighbouring vertices that have not been protected, while a constant number of vertices are protected at each time interval. In the version of the problem considered here, the firefighters are able to orient the edges of the graph before the fire breaks out, but the fire could start at any vertex. We consider this problem when played on a graph in one of several graph classes, and give upper and lower bounds on the number of vertices that can be saved. In particular, when one firefighter is available at each time interval, and the given graph is a complete graph, or a complete bipartite graph, we present firefighting strategies that are provably optimal. We also provide lower bounds on the number of vertices that can be saved as a function of the chromatic number, of the maximum degree, and of the treewidth of a graph. For a subcubic graph, we show that the firefighters can save all but two vertices, and this is best possible.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nick Brettell

Research overview

Is this your work?

10 publications

Cyclic matroids

$N$ -detachable pairs in 3-connected matroids III: the theorem

$N$ -detachable pairs in 3-connected matroids I: unveiling $X$

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective

Excluded minors are almost fragile

On a generalisation of spikes

Colouring graphs with constraints on connectivity

Parameterized vertex deletion problems for hereditary graph classes with a block property

Orienting edges to fight fire in graphs

See the researcher in context

Building this map preview

Nick Brettell

Research overview

Is this your work?

10 publications

Cyclic matroids

NNN-detachable pairs in 3-connected matroids III: the theorem

NNN-detachable pairs in 3-connected matroids I: unveiling XXX

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Colouring (sP1+P5)(sP_1+P_5)(sP1​+P5​)-Free Graphs: a Mim-Width Perspective

Excluded minors are almost fragile

On a generalisation of spikes

Colouring graphs with constraints on connectivity

Parameterized vertex deletion problems for hereditary graph classes with a block property

Orienting edges to fight fire in graphs

See the researcher in context

Building this map preview

$N$ -detachable pairs in 3-connected matroids III: the theorem

$N$ -detachable pairs in 3-connected matroids I: unveiling $X$

Colouring $(sP_1+P_5)$ -Free Graphs: a Mim-Width Perspective