Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
本文提出新的约简技术和启发式方法，集成到精确求解器中，平均性能比此前方法提升两个数量级，并首次最优求解了DIMACS挑战赛的一个大规模基准实例。
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest in recent years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers---with steadily increasing performance. Continuing along this path, this article introduces several new algorithms, such as reduction techniques and heuristics and describes their integration into an exact solver. Based on the presented new algorithms and a new formulation, our solver is able to outperform previous methods by two orders of magnitude on average. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced. Although this article is set against the backdrop of improved practical solving, theoretical properties (such as $\mathcal{NP}$-hardness) of the algorithmic components will receive considerable attention.