Integer and Fractional Matchings.
Abstract
We examine the connections between maximum cardinality edge matchings in a graph and optimal solutions to the associated linear program, which we call maximum f-matchings (fractional matchings). We say that a maximum matching M separates an odd cycle with vertex set S, if M has no edge with exactly one end in S. An odd cycle is separable if it is separated by at least one maximum matching. We show that a graph G has a maximum f-matching that is integer, if and only if it has no separable odd cycles; the minimum number q of vertex-disjoint odd cycles for which a maximum f-matching has fractional components, equals the maximum number s of vertex-disjoint odd cycles, separated by a maximum matching; the difference between the cardinality of a maximum f-matching and that of a maximum matching in G is one half times s; any maximum f-matching with fractional components for a minimum number s of vertex-disjoint odd cycles defines a maximum matching obtainable from it in s steps; and if a maximum f-matching has fractional components for a set Q of odd cycles that is not minimum, there exists another maximum f-matching with fractional components for a minimum-cardinality set S of odd cycles, such that S is a subset of Q, absival Q/S is even, and the cycles in Q/S are pairwise connected by alternating paths. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1979
- Accession Number
- ADA067067
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University