Erdős–Pósa Theorem

In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph:

* The size of the largest collection of vertex-disjoint cycles contained in the graph;
* The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle.

Motivation and statement

In many applications, we are interested in finding a minimum feedback vertex set in a graph: a small set that includes one vertex from every cycle, or, equivalently, a small set of vertices whose removal destroys all cycles. This is a hard computational problem; if we are not able to solve it exactly, we can instead try to find lower and upper bounds on the size of the minimum feedback vertex set.

One approach to find lower bounds is to find a collection of vertex-disjoint cycles in a graph. For example, consider the graph in Figure 1. The cycles A-B-C-F-A and G-H-I-J-G share no vertices. As a result, if we want to remove vertices and destroy all cycles in the graph, we must remove at least two vertices: one from the first cycle and one from the second. This line of reasoning generalizes: if we can find vertex-disjoint cycles in a graph, then every feedback vertex set in the graph must have at least vertices.

Unfortunately, in general, this bound is not tight: if the largest collection of vertex-disjoint cycles in a graph contains cycles, then it does not necessarily follow that there is a feedback vertex set of size . The graph in Figure 1 is an example of this: even if we destroy cycle G-H-I-J-G by removing one of the vertices G, H, I, or J, we cannot destroy all four of the cycles A-B-C-F-A, A-B-E-F-A, B-C-D-E-B, and C-D-E-F-C by removing only one more vertex. Any minimum feedback vertex set in the graph in Figure 1 has three vertices: for example, the three vertices A, C, and G.

It is possible to construct examples in which the gap between the two quantities - the size of the largest collection of vertex-disjoint cycles, and the size of the smallest feedback vertex set - is arbitrarily large. The Erdős–Pósa theorem says that despite this, knowing one quantity does put lower ''and'' upper bounds on the other quantity. Formally, the theorem states that there exists a function $f : \mathbb \rarr \mathbb$ such that for each positive integer , every graph either

* contains a collection of vertex-disjoint cycles, or
* has a feedback vertex set of at most vertices.

For example, suppose we have determined that for the graph in Figure 1, there is a collection of 2 vertex-disjoint cycles, but no collection of 3 vertex-disjoint cycles. Our earlier argument says that the smallest feedback vertex set must have at least 2 vertices; the Erdős–Pósa theorem says that the smallest feedback vertex set must have at most vertices.

In principle, many functions could satisfy the theorem. For the purpose of discussing bounds on how large needs to be, we define the ''Erdős–Pósa function'' to give, for each positive integer , the least value of for which the statement of the theorem holds.

Bounds on the Erdős–Pósa function

In addition to proving that the function exists, obtained the bounds for some constants and . In Big O notation, .

A previous unpublished result of Béla Bollobás stated : in simpler terms, any graph which does not contain two vertex-disjoint cycles has a feedback vertex set of at most three vertices. One example showing that is , the complete graph on 5 vertices. Here, because any cycle must contain at least three vertices, and there are only 5 vertices total, any two cycles must overlap in at least one vertex. On the other hand, a set of only two vertices cannot be a feedback vertex set because the other three vertices will form a cycle: a feedback vertex set must contain at least three vertices.

The result that was first published by , who also gave a complete characterization of the case : that is, he described the graphs which, like the example of given above, do not contain two vertex-disjoint cycles. Later, proved and .

Erdős–Pósa property

A family of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function $f : \mathbb \rarr \mathbb$ such that for every (hyper-)graph and every integer one of the following is true:

* contains vertex-disjoint subgraphs each isomorphic to a graph in ; or
* contains a vertex set of size at most such that has no subgraph isomorphic to a graph in .

The definition is often phrased as follows. If one denotes by the maximum number of vertex disjoint subgraphs of isomorphic to a graph in and by the minimum number of vertices whose deletion from leaves a graph without a subgraph isomorphic to a graph in , then , for some function $f : \mathbb \rarr \mathbb$ not depending on .

Rephrased in this terminology, the Erdős–Pósa theorem states that the family consisting of all cycles has the Erdős–Pósa property, with bounding function . Robertson and Seymour (1986) generalized this considerably. Given a graph , let () denote the family of all graphs that contain as a minor. As a corollary of their grid minor theorem, Robertson and Seymour proved that () has the Erdős–Pósa property if and only if is a planar graph. Moreover, it is now known that the corresponding bounding function is if is a forest , while for every other planar graph .

When we take to be a triangle, the family () consists of all graphs that contain at least one cycle, and a vertex set such that has no subgraph isomorphic to a graph in () is exactly a feedback vertex set. Thus, the special case where is a triangle is equivalent to the Erdős–Pósa theorem.

References

*
*
*
*
*
*

See also

* Pósa theorem (1962).

A list of graph classes for which the Erdös-Pósa property is known to (not) hold.
{{DEFAULTSORT:Erdos-Posa theorem
Theorems in graph theory