Linear programming and the worst-case analysis of greedy algorithms on cubic graphs (Q612969)

We introduce a technique using linear programming that may be used to analyse the worst-case performance of a class of greedy heuristics for certain optimisation problems on regular graphs. We demonstrate the use of this technique on heuristics for bounding the size of a minimum maximal matching (MMM), a minimum connected dominating set (MCDS) and a minimum independent dominating set (MIDS) in cubic graphs. We show that for \(n\)-vertex connected cubic graphs, the size of an MMM is at most \(9n/20+O(1)\), which is a new result. We also show that the size of an MCDS is at most \(3n/4+ O(1)\) and the size of a MIDS is at most \(29n/70+ O(1)\). These results are not new, but earlier proofs involved rather long ad-hoc arguments. By contrast, our method is to a large extent automatic and can apply to other problems as well. We also consider n-vertex connected cubic graphs of girth at least 5 and for such graphs we show that the size of an MMM is at most \(3n/7+O(1)\), the size of an MCDS is at most \(2n/3+O(1)\) and the size of a MIDS is at most \(3n/8+O(1)\).