A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem

In this article we consider the Node-Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node-induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually em-ploy a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node-cut inequali-ties, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition-based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. Finally, we show that the well-known indegree equalities are implied by the lifted partition inequalities.