Improved Computational Approaches and Heuristics for Zero Forcing

Boris Brimkov (), Derek Mikesell () and Illya V. Hicks ()
Additional contact information
Boris Brimkov: Department of Mathematics and Statistics, Slippery Rock University, Slippery Rock, Pennsylvania 16057
Derek Mikesell: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005
Illya V. Hicks: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1384-1399

Abstract: Zero forcing is a graph coloring process based on the following color change rule: all vertices of a graph G are initially colored either blue or white; in each timestep, a white vertex turns blue if it is the only white neighbor of some blue vertex. A zero forcing set of G is a set of blue vertices such that all vertices eventually become blue after iteratively applying the color change rule. The zero forcing number Z ( G ) is the cardinality of a minimum zero forcing set. In this paper, we propose novel exact algorithms for computing Z ( G ) based on formulating the zero forcing problem as a two-stage Boolean satisfiability problem. We also propose several heuristics for zero forcing based on iteratively adding blue vertices which color a large part of the remaining white vertices. These heuristics are used to speed up the exact algorithms and can also be of independent interest in approximating Z ( G ) . Computational results on various types of graphs show that, in many cases, our algorithms offer a significant improvement on the state-of-the-art algorithms for zero forcing. Summary of Contribution: This paper proposes novel algorithms and heuristics for an NP-hard graph coloring problem that has numerous applications. Our exact methods combine Boolean satisfiability modeling with a constraint generation framework commonly used in operations research. The paper also includes an analysis of the facets of the polytope associated with this problem and decomposition techniques which can reduce the size of the problem. Our computational approaches are implemented and tested on a wide variety of graphs and are compared with the state-of-the-art algorithms from the literature. We show that our proposed algorithms based on Boolean satisfiability, in conjunction with the heuristics and order-reduction techniques, yield a significant speedup in some cases.

Keywords: zero forcing; Boolean satisfiability; heuristic; constraint generation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1032 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1384-1399

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().