Integer and fractional packing of families of graphs
Raphael Yuster · Random Structures and Algorithms · 2004
Abstract Let F be a family of graphs. For a graph G, the F‐packing number, denoted νF(G), is the maximum number of pairwise edge‐disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F‐packing of G if σe∈H∈F ψ(H) ≤ 1 for each e ∈ E(G). The fractional F‐packing number, denoted νF* (G), is defined to be the maximum value of σ ψ(H) over all fractional F‐packings ψ. Our main result is that νF* (G)−νF(G) = o(|V(G)|2). Furthermore, a set of νF(G)−o(|V(G)|2) edge‐disjoint elements of F in G can be found in randomized polynomial time. For the special case F = {H0} we obtain a simpler proof of a recent difficult result of Haxell and Rödl [Combinatorica 21 (2001), 13–38] that ν* (G) − ν (G) = o(|V(G)|2). Their result can be implemented in deterministic polynomial time. We also prove that the error term o(|V(G)|2) is asymptotically tight. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005