The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species

Authors

  • Katherine Lai Cornell University
  • Carla Gomes Cornell University
  • Michael Schwartz USDA Forest Service Rocky Mountain Research Station
  • Kevin McKelvey USDA Forest Service Rocky Mountain Research Station
  • David Calkin USDA Forest Service Rocky Mountain Research Station
  • Claire Montgomery Oregon State University

Abstract

The conservation of wildlife corridors between existing habitat preserves is important for combating the effects of habitat loss and fragmentation facing species of concern. We introduce the Steiner Multigraph Problem to model the problem of minimum-cost wildlife corridor design for multiple species with different landscape requirements. This problem can also model other analogous settings in wireless and social networks. As a generalization of Steiner forest, the goal is to find a minimum-cost subgraph that connects multiple sets of terminals. In contrast to Steiner forest, each set of terminals can only be connected via a subset of the nodes. Generalizing Steiner forest in this way makes the problem NP-hard even when restricted to two pairs of terminals. However, we show that if the node subsets have a nested structure, the problem admits a fixed-parameter tractable algorithm in the number of terminals. We successfully test exact and heuristic solution approaches on a wildlife corridor instance for wolverines and lynx in western Montana, showing that though the problem is computationally hard, heuristics perform well, and provably optimal solutions can still be obtained.

Downloads

Published

2011-08-04

How to Cite

Lai, K., Gomes, C., Schwartz, M., McKelvey, K., Calkin, D., & Montgomery, C. (2011). The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1357-1364. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7809

Issue

Section

Special Track on Computational Sustainability and AI