Mathematics – Combinatorics
Scientific paper
2003-12-03
Mathematics
Combinatorics
18 pages
Scientific paper
In this paper, we study the relations between the numerical structure of the optimal solutions of a convex programming problem defined on the edge set of a simple graph and the stability number (i.e. the maximum size of a subset of pairwise non-adjacent vertices) of the graph. Our analysis shows that the stability number of every graph G can be decomposed in the sum of the stability number of a subgraph containing a perfect 2-matching (i.e. a system of vertex-disjoint odd-cycles and edges covering the vertex-set) plus a term computable in polynomial time. As a consequence, it is possible to bound from above and below the stability number in terms of the matching number of a subgraph having a perfect 2-matching and other quantities computable in polynomial time. Our results are closely related to those by Lorentzen, Balinsky, Spielberg, and Pulleyblank on the linear relaxation of the vertex-cover problem. Moreover, The convex programming problem involved has important applications in information theory and extremal set theory where, as a graph capacity formula, has been used to answer a longstanding open question about qualitatively independet sets in the sense of Renyi (L. Gargano, J. K{\"o}rner, and U. Vaccaro, "Sperner capacities", Graphs and combinatorics, 9:31-46, 1993).
No associations
LandOfFree
A Splitting Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Splitting Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Splitting Lemma will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-188024