Binary Programming Formulations for the Upper Domination Problem

We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination. In particular, no binary programming formulations for Upper Domination have been described in literature, although such formulations have proved quite successful for other kinds of domination problems. We introduce two such binary programming formulations, and compare their performance on various kinds of graphs. We demonstrate that the first performs better in most cases, but the second performs better for very sparse graphs. Also included is a short proof that the upper domination of any generalized Petersen graph P(n,k) is equal to n.Comment: 9 pages, 2 figure