A Splitting Lemma
| dc.creator | Greco, G. | |
| dc.date | 2003-12-03 | |
| dc.date | 2003-12-05 | |
| dc.date.accessioned | 2026-07-07T05:03:31Z | |
| dc.date.available | 2026-07-07T05:03:31Z | |
| dc.description | 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{ö}rner, and U. Vaccaro, "Sperner capacities", Graphs and combinatorics, 9:31-46, 1993). | |
| dc.description | 18 pages | |
| dc.identifier | https://arxiv.org/abs/math/0312086 | |
| dc.identifier | http://arxiv.org/abs/math/0312086 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69453 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C70;05d05;68R01 | |
| dc.title | A Splitting Lemma | |
| dc.type | text |