an LP relaxation
Many hard combinatorial problems are naturally about yes/no choices: include this vertex or not, pick this set or not, use this edge or not. Written as math, each decision is a variable forced to be 0 or 1, and the constraint 'must be 0 or 1' is precisely what makes the problem NP-hard. An LP relaxation performs a deliberate act of cheating-on-purpose: it RELAXES that integrality demand, letting each variable be any real number between 0 and 1. The fractional problem that results is a linear program, which we can solve to optimality in polynomial time.
Here is the maneuver on vertex cover. Give each vertex i a variable x_i. We want to minimize the sum of x_i (the number of chosen vertices), subject to: for every edge (i, j), x_i + x_j >= 1 (each edge must have a chosen endpoint), and x_i in {0, 1}. That last constraint makes it integer programming, NP-hard. The relaxation simply swaps x_i in {0,1} for 0 <= x_i <= 1. Now it is a linear program — linear objective, linear inequalities, continuous variables — and linear programs are solvable efficiently. A vertex can now be 'half chosen' (x_i = 0.5), which is meaningless physically but mathematically fine. The key, dependable fact is this: because the relaxation allows MORE solutions (every integer solution is still allowed, plus fractional ones), its optimum can only be better or equal. So for a minimization problem, LP-OPT <= integer-OPT — the relaxation's value is a computable lower bound on the true optimum.
That lower bound is the whole reason to relax. It hands you a concrete, polynomial-time number to compare your algorithm against — the same surrogate-for-OPT role played by matchings and MSTs elsewhere, but now produced by a completely general, mechanical method that applies to almost any 0/1 problem you can write down. The catch is that the LP's answer is usually fractional and so not a real solution; you still have to convert those fractions back into honest 0/1 decisions, which is the job of rounding. The gap between LP-OPT and integer-OPT (the integrality gap) limits how good any rounding can be, and is itself a deep object of study.
On a triangle (3 vertices, every pair joined), the integer optimum cover is 2 vertices. The LP relaxation can set every x_i = 0.5: each edge gets 0.5 + 0.5 = 1, all constraints satisfied, total = 1.5. So LP-OPT = 1.5 <= 2 = integer-OPT — a fractional cover that no physical cover can match, but a valid lower bound.
Drop 'x must be 0/1' to '0 <= x <= 1': now solvable in poly time, and its optimum bounds OPT.
The relaxation's optimum is a bound, not a solution: it is usually fractional and physically meaningless (half a vertex). Its value is what you use — as a lower bound on a minimization OPT — and you still need rounding to recover an actual 0/1 answer.