The Problem:
The vertex cover problem VC: Min Sum wi xi s.t forall edge ij xi+xj>=1.

Effective progress:
To get 1-effective approximation you need tight constreint.
E.g. Say you know that x1+x2+2x3=2 you can change the objective function
from COST =  w1x1+    w2x2+    w3x3+    w4x4+w5x5+...+wnxn
 to  COST' = (w1-1)x1+(w2-1)x2+(w3-2)x3+w4x4+w5x5+...+wnxn
Oviously COST-COST'=2
Notice that multiplying tight constreint is valid and therefore
youcould have multiply it by Min(w1,w2,w3/2) and this whay
one of the coaficions would vanist in the new objective function.

Getting tight constreint:
First atempt.
       Add a variable xij, wij.
       Change constreint to tight xi+xj+xij=2
       Problems: if wij starts with 0, no progress can be made
                               if wij>0 than
                                       if wij>=wi,wj than take all vertices.
                                       else after LR wij=0 and we have the same problem
Second (and last) atempt:
       Add a variable xij, wij.
       Change constreint to tight xi+xj-xij=1 //interpetation xij=overcover
       we stard wij=0 and define COST = w1x1+...+wnxn + w12x12+...+wixj+..
   Example: before: 7---0---3 After: 4--3--0 and new cost
                               COST'=COST-(3x1+3x1-3x12)=COST-3
       In general: if 12 is an edge and w1,w2>0
                               we select w'=Min{w1,w2}
                               and w1-=w1; w2-=w'; w12+=w'; SO that COST'=COST-w1
       After we done:
               Good news1: every edge has zero weight endpoint
               Good news2: Total COST is reduced.
               Bad news1: some edges has positive weight
               Bad news2: We are not sure if COST reduced to zerow.

More tigh constreints:
       We new kind of tight constreint (TC).
       Idea: linear combination of TCs gives TC.
       Example1: 1--12--2--23--3 gives TC123=TC12-TC23 gives x1-x12+x23-x3=0
               Good news: even if w2=0 we may use this TC.
               Bad news: This TC gives us not progress in COST.
       Example2: 1--12--2--23--3--34--4
               gives TC1234=TC12-TC23+TC34 gives x1-x12+x23-x34+x4=1
               Good news: If found make a progress in COST
               Bad news: We need +--?--?--+--?--?--+, what if not found?
       Generalization: Odd path: 1--12--2--23--3--34--4--...--2k
               gives TC1234..2k=TC12-TC23+TC34-T45+...+T2k-1_2k
               gives x1-x12+x23-x34+x4-...+x2k=1
               Good news: If found make a progress in COST
               Bad news: We need +--?--?--+--?--?--+..., Alternation path.
       Q: is this sufficient?
       A: Almost. Just generalized not non simple paths.

Claim: If no alternation exists then COST=0.
       Define A0 = all positive vertices
               A1 = N(A0), A2= N+(A1) ... i.e. A_odd = N(A_previous) A_even= N+(A_previous)
       Claim1: No edges in A2i
       Claim2: No positive edges in A2i+1
       Define L= union of A2i M union of A2i+1 R all the rest
       Claims: No edges in L
                        all edges in E(M)-E(L) are zeros;
   L={+...+++00...000} M={00...0000} R={00...000}
       E(L,L)={}  W(E(M,M))=0 W(E(M,R))=0
The following is feasible fractional solution:
       xi=1   for all i in L
       xi=0   for all i in M;  xij=0   for ij in MxM
       xi=1/2 for all i in R;  xij=1/2 for ij in MxM
       xi=0
COST = 0;
The following is partial feasible integral solution:
       xi=1   for all i in L
       xi=0   for all i in M;  xij=0   for ij in MxM
Proof: W(OPT(L,M))>=W(E(L,M))
       and every integral solution C can be replaced C-L+M


HALL:
M in E is a perfect matching if G(M)=G
B(X,Y,E) is perfect if it has a perfect matching
X' in X is defect if |N(x)| < |X|
B is defected if it contain a defect
Hall: B is prefect <===> B is not defected.
Proof:
===> is trivial
<=== Run VC(0,1/2,1). No need for 1/2 and all wij is 0/1.
if ++ then L is defect and therefore B is not perfect.
 
Generalized:
G, C
Perfect if existt wij s.t. ci is homogenious w.r.t. w.
X i.s. is defect if C(N(X)) < (C(X)
G is defected if...
Hall: B is prefect <===> B is not defected.
===> is trivial
<==== Run VC(0,1/2,1)
if ++ the L is defect.