Erdős–Pósa theorem

Template:Short description 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 Template:Mvar vertex-disjoint cycles in a graph, then every feedback vertex set in the graph must have at least Template:Mvar vertices.

Figure 1: in red, two vertex-disjoint cycles, A-B-C-F-A and G-H-I-J-G. In blue, a feedback vertex set {A,C,G}.

Unfortunately, in general, this bound is not tight: if the largest collection of vertex-disjoint cycles in a graph contains Template:Mvar cycles, then it does not necessarily follow that there is a feedback vertex set of size Template:Mvar. 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{N}\to \mathbb{N}$ such that for each positive integer Template:Mvar, every graph either

• contains a collection of Template:Mvar vertex-disjoint cycles, or
• has a feedback vertex set of at most Template:Math 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 Template:Math vertices.

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

Bounds on the Erdős–Pósa function

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

A previous unpublished result of Béla Bollobás stated Template:Math: 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 Template:Math is Template:Mvar, 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 Template:Math was first published by Template:Harvtxt, who also gave a complete characterization of the case Template:Math: that is, he described the graphs which, like the example of Template:Mvar given above, do not contain two vertex-disjoint cycles. Later, Template:Harvtxt proved Template:Math and Template:Math.

Erdős–Pósa property

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

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

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

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

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

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal

See also

• Pósa theorem (1962).

External links

• List of graph classes for which the Erdös-Pósa property is known to (not) hold