zbMATH — the first resource for mathematics

The rooted maximum node-weight connected subgraph problem. (English) Zbl 1382.90108
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 300-315 (2013).
Summary: Given a connected node-weighted (di)graph, with a root node \(r\), and a (possibly empty) set of nodes \(R\), the rooted maximum node-weight connected subgraph problem (RMWCS) is the problem of finding a connected subgraph rooted at \(r\) that connects all nodes in \(R\) with maximum total weight. In this paper we consider the RMWCS as well as its budget-constrained version, in which also non-negative costs of the nodes are given, and the solution is not allowed to exceed a given budget. The considered problems belong to the class of network design problems and have applications in various different areas such as wildlife preservation planning, forestry, system biology and computer vision.
We present three new integer linear programming formulations for the problem and its variant which are based on node variables only. These new models rely on a different representation of connectivity than the one previously presented in the RMWCS literature that rely on a transformation into the Steiner Arborescence problem. We theoretically compare the strength of the proposed and the existing formulations, and show that one of our models preserves the tight LP bounds of the previously proposed cut set model of Dilkina and Gomes. Moreover, we study the rooted connected subgraph polytope in the natural space of node variables. We conduct a computational study and (empirically) compare the theoretically strongest one of our formulations with the one previously proposed using ad-hoc branch-and-cut implementations.
For the entire collection see [Zbl 1263.68017].

90C35 Programming involving graphs or networks
05C22 Signed and weighted graphs
05C40 Connectivity
90C27 Combinatorial optimization
Full Text: DOI