An Instance-specific Hardness Measure for Minimum Vertex Cover
Lili Wang, Jinchuan Cui · Shuxue de shijian yu renshi · 2017
Minimum vertex cover is NP-complete, when the scale n is large, it is intractable in the point of complexity. But a lot of examples show that, even if instances have the same size, they will take different time due to their different structure. So it is necessary to establish a harness measure approach of instance-specific. we give an instance-specific hardness measure for Minimum vertex cover based on parameterized algorithm. The parameterized algorithm can be used to solve decision problem of Minimum vertex cover with running time O*(2.314k-vc*（G）).When parameter k is constant, the Minimum vertex cover can be solved in polynomial time, but When k is a function of n, it is intractable. We use approximate algorithm of Minimum vertex cover — linear programming relaxation to estimate the range of parameters k for each instance. we can predict the running time of any instance, in polynomial time, before solving it. The problem in planar graph can be measured more precisely with EPTASalgorithm.