Source author record

Paul Wollan

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics Computational Complexity math.HO math.PR

Catalog footprint

Research overview

20works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Quickly excluding a non-planar graph

A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph $G$ with no minor isomorphic to a fixed graph $H$ has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $n\times n$ grid minor $J$ of $G$ the graph $G$ has a a $k$ -near embedding in a surface $Σ$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Σ$ . Here a $k$ -near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Σ$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$ . The original and only proof so far is quite long and uses many results developed in the Graph Minors series. We give a proof that uses only our earlier paper [A new proof of the flat wall theorem, {\it J.~Combin.\ Theory Ser.\ B \bf 129} (2018), 158--203] and results from graduate textbooks. Our proof is constructive and yields a polynomial time algorithm to construct such a structure. We also give explicit constants for the structure theorem, whereas the original proof only guarantees the existence of such constants.

preprint2016arXiv

A New Proof of the Flat Wall Theorem

We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t,r>0 be integers, and let R=49152t^{24}(40t^2+r). An r-wall is obtained from a (2r x r)-grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two that existed before the subdivision are called the pegs of the r-wall. Let G be a graph with no K_t minor, and let W be an R-wall in G. We prove that there exist a subset A of V(G) of size at most 12288t^{24} and an r-subwall W' of W such that V(W') is disjoint from A and W' is a flat wall in G-A in the following sense. There exists a separation (X,Y) of G-A such that X\cap Y is a subset of the vertex set of the cycle C' that bounds the outer face of W', V(W') is a subset of Y, every peg of W' belongs to X and the graph G[Y] can almost be drawn in the unit disk with the vertices X\cap Y drawn on the boundary of the disk in the order determined by C'. Here almost means that the assertion holds after repeatedly removing parts of the graph separated from X\cap Y by a cutset Z of size at most three, and adding all edges with both ends in Z. Our proof gives rise to an algorithm that runs in polynomial time even when r and t are part of the input instance. The proof is self-contained in the sense that it uses only results whose proofs can be found in textbooks.

preprint2016arXiv

Half-integral linkages in highly connected directed graphs

We study the half-integral $k$ -Directed Disjoint Paths Problem ( $\tfrac12$ kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$ , and the input graph is $L$ -strongly connected, for any $L\geq 1$ . We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\geq 2$ there exists $L(k)$ such that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^c)$ for a $L(k)$ -strongly connected directed graph $G$ . As the function $L(k)$ grows rather quickly, we also show that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^{f(k)})$ in $(36k^3+2k)$ -strongly connected directed graphs. We also show that for each $ε<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $εk$ .

preprint2016arXiv

The Erdos-Posa Property for Directed Graphs

A classical result by Erdos and Posa states that there is a function $f: {\mathbb N} \rightarrow {\mathbb N}$ such that for every $k$ , every graph $G$ contains $k$ pairwise vertex disjoint cycles or a set $T$ of at most $f(k)$ vertices such that $G-T$ is acyclic. The generalisation of this result to directed graphs is known as Younger's conjecture and was proved by Reed, Robertson, Seymour and Thomas in 1996. This so-called Erdos-Posa-property can naturally be generalised to arbitrary graphs and digraphs. Robertson and Seymour proved that a graph $H$ has the Erdos-Posa-property if, and only if, $H$ is planar. In this paper we study the corresponding problem for digraphs. We obtain a complete characterisation of the class of strongly connected digraphs which have the Erdos-Posa-property (both for topological and butterfly minors). We also generalise this result to classes of digraphs which are not strongly connected. In particular, we study the class of vertex-cyclic digraphs (digraphs without trivial strong components). For this natural class of digraphs we obtain a nearly complete characterisation of the digraphs within this class with the Erdos-Posa-property. In particular we give positive and algorithmic examples of digraphs with the Erdos-Posa-property by using directed tree decompositions in a novel way.

preprint2015arXiv

Space proof complexity for random 3-CNFs

We investigate the space complexity of refuting $3$ -CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random $3$ -CNF $ϕ$ in $n$ variables requires, with high probability, $Ω(n)$ distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation $ϕ$ requires, with high probability, $Ω(n)$ clauses each of width $Ω(n)$ to be kept at the same time in memory. This gives a $Ω(n^2)$ lower bound for the total space needed in Resolution to refute $ϕ$ . These results are best possible (up to a constant factor). The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs $G$ with bipartition $(L,R)$ and left-degree at most 3, $L$ can be covered by certain families of disjoint paths, called VW-matchings, provided that $L$ expands in $R$ by a factor of $(2-ε)$ , for $ε< 1/23$ .

preprint2014arXiv

A structure theorem for strong immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion.

preprint2014arXiv

An exact characterization of tractable demand patterns for maximum disjoint path problems

We study the following general disjoint paths problem: given a supply graph $G$ , a set $T\subseteq V(G)$ of terminals, a demand graph $H$ on the vertices $T$ , and an integer $k$ , the task is to find a set of $k$ pairwise vertex-disjoint valid paths, where we say that a path of the supply graph $G$ is valid if its endpoints are in $T$ and adjacent in the demand graph $H$ . For a class $\mathcal{H}$ of graphs, we denote by $\mathcal{H}$ -Maximum Disjoint Paths the restriction of this problem when the demand graph $H$ is assumed to be a member of $\mathcal{H}$ . We study the fixed-parameter tractability of this family of problems, parameterized by $k$ . Our main result is a complete characterization of the fixed-parameter tractable cases of $\mathcal{H}$ -Maximum Disjoint Paths for every hereditary class $\mathcal{H}$ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph $H$ (a skew biclique is a bipartite graph on vertices $a_1$ , $\dots$ , $a_n$ , $b_1$ , $\dots$ , $b_n$ with $a_i$ and $b_j$ being adjacent if and only if $i\le j$ ). Specifically, we prove the following classification for every hereditary class $\mathcal{H}$ . 1. If $\mathcal{H}$ does not contain every matching and does not contain every skew biclique, then $\mathcal{H}$ -Maximum Disjoint Paths is FPT. 2. If $\mathcal{H}$ does not contain every matching, but contains every skew biclique, then $\mathcal{H}$ -Maximum Disjoint Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdős-Pósa property. 3. If $\mathcal{H}$ contains every matching, then $\mathcal{H}$ -Maximum Disjoint Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdős-Pósa property.

preprint2014arXiv

Immersions in highly edge connected graphs

We consider the problem of how much edge connectivity is necessary to force a graph G to contain a fixed graph H as an immersion. We show that if the maximum degree in H is D, then all the examples of D-edge connected graphs which do not contain H as a weak immersion must have a tree-like decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique K_t as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain K_t as a strong immersion.

preprint2014arXiv

Linkages in Large Graphs of Bounded Tree-Width

We show that all sufficiently large (2k+3)-connected graphs of bounded tree-width are k-linked. Thomassen has conjectured that all sufficiently large (2k+2)-connected graphs are k-linked.

preprint2014arXiv

Space proof complexity for random $3$ -CNFs via a $(2-ε)$ -Hall's Theorem

We investigate the space complexity of refuting $3$ -CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$ -CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random $3$ -CNF $ϕ$ in $n$ variables requires, with high probability, $Ω(n/\log n)$ distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation $ϕ$ requires, with high probability, $Ω(n/\log n)$ clauses each of width $Ω(n/\log n)$ to be kept at the same time in memory. This gives a $Ω(n^2/\log^2 n)$ lower bound for the total space needed in Resolution to refute $ϕ$ . The main technical innovation is a variant of Hall's theorem. We show that in bipartite graphs $G$ with bipartition $(L,R)$ and left-degree at most 3, $L$ can be covered by certain families of disjoint paths, called $(2,4)$ -matchings, provided that $L$ expands in $R$ by a factor of $(2-ε)$ , for $ε< \frac{1}{23}$ .

preprint2014arXiv

The structure of graphs not admitting a fixed immersion

We present an easy structure theorem for graphs which do not admit an immersion of the complete graph. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall.

preprint2013arXiv

Axioms for infinite matroids

We give axiomatic foundations for non-finitary infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. This completes the solution to a problem of Rado of 1966.

preprint2013arXiv

K_6 minors in 6-connected graphs of bounded tree-width

We prove that every sufficiently big 6-connected graph of bounded tree-width either has a K_6 minor, or has a vertex whose deletion makes the graph planar. This is a step toward proving that the same conclusion holds for all sufficiently big 6-connected graphs. Jorgensen conjectured that it holds for all 6-connected graphs.

preprint2013arXiv

Rooted grid minors

Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid. This is a lemma for use in a later paper.

preprint2012arXiv

K_6 minors in large 6-connected graphs

Jorgensen conjectured that every 6-connected graph with no K_6 minor has a vertex whose deletion makes the graph planar. We prove the conjecture for all sufficiently large graphs.

preprint2011arXiv

Finite connectivity in infinite matroids

We introduce a connectivity function for infinite matroids with properties similar to the connectivity function of a finite matroid, such as submodularity and invariance under duality. As an application we use it to extend Tutte's linking theorem to finitary and to co-finitary matroids.

preprint2011arXiv

Isomorphism for even cycle matroids - I

A seminal result by Whitney describes when two graphs have the same cycles. We consider the analogous problem for even cycle matroids. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. We consider the problem of determining the relation between two signed graphs representing the same even cycle matroid. We refer to this problem as the Isomorphism Problem for even cycle matroids. We present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that, up to simple operations, any two signed graphs representing the same even cycle matroid are either in one of these classes, or related by a modification of an operation for graphic matroids, or belonging to a small set of examples.

preprint2010arXiv

Finding topological subgraphs is fixed-parameter tractable

We show that for every fixed undirected graph $H$ , there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$ , if $G$ contains $H$ as a topological subgraph (that is, a subdivision of $H$ is subgraph of $G$ ). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every $H$ we obtain an $O(|V(G)|^3)$ time algorithm that tests if there is an immersion of $H$ into a given graph $G$ . This answers another open question raised by Downey and Fellows in 1992.

preprint2010arXiv

The Erdös-Pósa property for clique minors in highly connected graphs

We prove the existence of a function f: N^2 -> N such that for all p,k in N every (k(p-3) + 14p+14) - connected graph either has k disjoint K_p minors or contains a set of at most f(p,k) vertices whose deletion kills all its K_p minors. For fixed p > 4, the connectivity bound of about k(p-3) is smallest possible, up to an additive constant: if we assume less connectivity in terms of k, there will be no such function f.

preprint2008arXiv

Voting in agreeable societies

When can a majority of voters find common ground, that is, a position they all agree upon? How does the shape of the political spectrum influence the outcome? When mathematical objects have a social interpretation, the associated theorems have social applications. In this article we give examples of situations where sets model preferences and develop extensions of classical theorems about convex sets, such as Helly's theorem, that can be used in the analysis of voting in "agreeable" societies.

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.

Paul Wollan

Research overview

Is this your work?

20 publications

Quickly excluding a non-planar graph

A New Proof of the Flat Wall Theorem

Half-integral linkages in highly connected directed graphs

The Erdos-Posa Property for Directed Graphs

Space proof complexity for random 3-CNFs

A structure theorem for strong immersions

An exact characterization of tractable demand patterns for maximum disjoint path problems

Immersions in highly edge connected graphs

Linkages in Large Graphs of Bounded Tree-Width

Space proof complexity for random $3$ -CNFs via a $(2-ε)$ -Hall's Theorem

The structure of graphs not admitting a fixed immersion

Axioms for infinite matroids

K_6 minors in 6-connected graphs of bounded tree-width

Rooted grid minors

K_6 minors in large 6-connected graphs

Finite connectivity in infinite matroids

Isomorphism for even cycle matroids - I

Finding topological subgraphs is fixed-parameter tractable

The Erdös-Pósa property for clique minors in highly connected graphs

Voting in agreeable societies

See the researcher in context

Building this map preview

Paul Wollan

Research overview

Is this your work?

20 publications

Quickly excluding a non-planar graph

A New Proof of the Flat Wall Theorem

Half-integral linkages in highly connected directed graphs

The Erdos-Posa Property for Directed Graphs

Space proof complexity for random 3-CNFs

A structure theorem for strong immersions

An exact characterization of tractable demand patterns for maximum disjoint path problems

Immersions in highly edge connected graphs

Linkages in Large Graphs of Bounded Tree-Width

Space proof complexity for random 333-CNFs via a (2−ε)(2-ε)(2−ε)-Hall's Theorem

The structure of graphs not admitting a fixed immersion

Axioms for infinite matroids

K_6 minors in 6-connected graphs of bounded tree-width

Rooted grid minors

K_6 minors in large 6-connected graphs

Finite connectivity in infinite matroids

Isomorphism for even cycle matroids - I

Finding topological subgraphs is fixed-parameter tractable

The Erdös-Pósa property for clique minors in highly connected graphs

Voting in agreeable societies

See the researcher in context

Building this map preview

Space proof complexity for random $3$ -CNFs via a $(2-ε)$ -Hall's Theorem