Minimum vertex cover in ball graphs through local search

Using local search method, this paper provides a polynomial time approximation scheme for the minimum vertex cover problem on <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$d$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>d</mi> </math> </EquationSource> </InlineEquation>-dimensional ball graphs where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$d \ge 3$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math> </EquationSource> </InlineEquation>. The key to the proof is a new separator theorem for ball graphs in higher dimensional space. Copyright Springer Science+Business Media New York 2014