Optimization Online


A Note on ``A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs"

Hamidreza Validi (hamidreza.validi***at***okstate.edu)
Austin Buchanan (buchanan***at***okstate.edu)

Abstract: In the paper ``A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs'' (Networks 39(1):53--60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (``A Zero-One Programming Model for Contiguous Land Acquisition.'' Geographical Analysis 34(4): 330-349, 2002).

Keywords: spanning tree; planar graph; planar dual; extended formulation; extension complexity; spanning arborescence; integer programming;

Category 1: Integer Programming

Category 2: Combinatorial Optimization

Citation: Published in Networks: https://onlinelibrary.wiley.com/doi/full/10.1002/net.21849 Freely available at: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxhdXN0aW5sYnVjaGFuYW58Z3g6M2U4YzBiZTY2NDVjMGYyYg


Entry Submitted: 07/04/2018
Entry Accepted: 07/05/2018
Entry Last Modified: 10/04/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society