Abstract
This paper presents a MaxSAT benchmark focused on identifying critical nodes
in AND/OR graphs. We use AND/OR graphs to model Industrial Control Systems
(ICS) as they are able to semantically grasp intricate logical
interdependencies among ICS components. However, identifying critical nodes in
AND/OR graphs is an NP-complete problem. We address this problem by efficiently
transforming the input AND/OR graph-based model into a weighted logical formula
that is then used to build and solve a Weighted Partial MaxSAT problem. The
benchmark includes 80 cases with AND/OR graphs of different size and
composition as well as the optimal cost and solution for each case.