A computational comparison of compact MILP formulations for the zero forcing number

Agostinho Agra, Jorge Orestes Cerdeira, Cristina Requejo

Research output: Contribution to journalArticle

5 Downloads (Pure)

Abstract

Consider a graph where some of its vertices are colored. A colored vertex with a single uncolored neighbor forces that neighbor to become colored. A zero forcing set is a set of colored vertices that forces all vertices to become colored. The zero forcing number is the size of a minimum forcing set. Finding the minimum forcing set of a graph is NP-hard. We give a new compact mixed integer linear programming formulation (MILP) for this problem, and analyze this formulation and establish relation to an existing compact formulation and to two variants. In order to solve large size instances we propose a sequential search algorithm which can also be used as a heuristic to derive upper bounds for the zero forcing number. A computational study using Xpress (a MILP solver) is conducted to test the performances of the discussed compact formulations and the sequential search algorithm. We report results on cubic, Watts–Strogatz and randomly generated graphs with 10, 20 and 30 vertices.

Original languageEnglish
Pages (from-to)169-183
JournalDiscrete Applied Mathematics
Volume269
Issue numberSI
DOIs
Publication statusPublished - 30 Sep 2019

Keywords

  • Compact formulations
  • Graphs
  • Mixed integer linear programming
  • Valid inequalities
  • Zero forcing

Fingerprint Dive into the research topics of 'A computational comparison of compact MILP formulations for the zero forcing number'. Together they form a unique fingerprint.

  • Cite this