A decomposition strategy for the vertex cover problem (Q1123907)

The authors introduce a strategy to decompose the minimum weight vertex cover problem on a graph \(G^ n\) into smaller subproblems. They use general results relative to clutters. The minimum vertex cover can be found by solving of a sequence of subproblems \(P_ j\) \((j=n,...,1)\). The vertex-cover problem is solved by solving n minimum weight vertex cover problems for minors. From the considerations the authors define a family of graphs for which the vertex cover problem is solvable in polynomial time.