Integer and fractional packing of families of graphs
- 16 November 2004
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 26 (1-2) , 110-118
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., 2005Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Integer and Fractional Packings in Dense GraphsCombinatorica, 2001
- The Probabilistic Method2000
- Nearly-perfect hypergraph packing is in NCInformation Processing Letters, 1996
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given GraphSIAM Journal on Computing, 1995
- The Algorithmic Aspects of the Regularity LemmaJournal of Algorithms, 1994
- Matchings and covers in hypergraphsGraphs and Combinatorics, 1988
- Near Perfect Coverings in Graphs and HypergraphsEuropean Journal of Combinatorics, 1985
- On a Packing and Covering ProblemEuropean Journal of Combinatorics, 1985