A Linear Algorithm for Universal Minimal Dominating Functions in Trees

A \({dominating \; function}\) is a feasible solution to the LP relaxation of the minimum dominating set \(0-1\) integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree \({T}\) can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in \({T}\), if one exists.