### 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 language | English |
---|---|

Pages (from-to) | 169-183 |

Journal | Discrete Applied Mathematics |

Volume | 269 |

Issue number | SI |

DOIs | |

Publication status | Published - 30 Sep 2019 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*,

*269*(SI), 169-183. https://doi.org/10.1016/j.dam.2019.03.027

}

*Discrete Applied Mathematics*, vol. 269, no. SI, pp. 169-183. https://doi.org/10.1016/j.dam.2019.03.027

**A computational comparison of compact MILP formulations for the zero forcing number.** / Agra, Agostinho; Cerdeira, Jorge Orestes; Requejo, Cristina.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Agra, Agostinho

AU - Cerdeira, Jorge Orestes

AU - Requejo, Cristina

N1 - This research was partially supported by the Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through projects UID/MAT/04106/2019 (A. Agra and C. Requejo) and UID/MAT/00297/2019 Q.O. Cerdeira).

PY - 2019/9/30

Y1 - 2019/9/30

N2 - 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.

AB - 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.

KW - Compact formulations

KW - Graphs

KW - Mixed integer linear programming

KW - Valid inequalities

KW - Zero forcing

UR - http://www.scopus.com/inward/record.url?scp=85064318649&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.03.027

DO - 10.1016/j.dam.2019.03.027

M3 - Article

VL - 269

SP - 169

EP - 183

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - SI

ER -