Alteration and randomized rounding

Take a finite simple graph with n vertices and m edges. Retain each vertex independently with probability p. The retained set has expected size np, while the number of edges inside it has expectation $mp^2$, because both endpoints of each edge must survive. Process the surviving edges in a fixed order, deleting one endpoint whenever both endpoints are still present. No edge remains at the end, so the result is independent. The total deletions are at most the initial number of surviving edges.

For every outcome, final size is at least retained size minus initial surviving-edge count. Taking expectations of this pointwise inequality gives a lower bound on expected final size and hence an outcome at least that large. This proof never asks that a large retained set and a small edge count occur separately with positive probability. They are coupled through one score. Removing a vertex can repair several defects at once, which only improves the lower bound; counting every original edge as a potential deletion is safe overcounting.

The quadratic score is concave when m is positive. Its unconstrained maximum occurs at p=n/(2m), but this is a probability only when it lies in the unit interval. If the proposed value exceeds one, use the boundary p=1 instead. If there are no edges, simply keep every vertex. A real-valued bound on the maximum independent-set size can be rounded up because that size is integer valued, provided the underlying inequality has been established exactly rather than from an unreliable rounded decimal.

The same repair logic applies to forbidden configurations in hypergraphs: sample vertices, count each unwanted configuration that survives, and remove one vertex from each surviving obstruction when needed. The survival probability depends on the number of distinct sampled vertices in the configuration. A proof must show that the repair operation destroys every forbidden configuration and does not introduce new ones. Vertex deletion is well suited to monotone forbidden-subgraph properties, whereas an operation that adds edges could create fresh defects and require a different analysis.

For a covering problem, suppose nonnegative fractional choices x have total mass at least one on each constraint. Select each item independently with probability the smaller of one and t times its fractional choice, for a chosen real t≥0. If a constraint contains an item selected with probability one, it is certainly covered. Otherwise independence bounds its failure probability by the exponential of minus t times its fractional mass, hence at most $e^{-t}$. With M constraints the probability of any uncovered constraint is at most $Me^{-t}$.

For nonnegative item costs, expected selected cost is at most t times fractional cost. Neither expected cost nor positive feasibility probability alone guarantees a feasible outcome at that expected cost. One option is to combine a cost-tail estimate with the feasibility union bound. Another is to repair each uncovered constraint by adding a known covering item, charging the expected repair cost explicitly. Such a repair needs those items and costs to exist, and overlapping repairs must not invalidate earlier constraints. This distinction prevents an expectation calculation from being mislabeled a complete approximation guarantee.