Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*

arXiv:2605.26938v1 Announce Type: new Abstract: Alignment-based conformance checking is the state-of-the-art approach for comparing observed process executions with normative process models. The standard exact solution relies on an A*-based heuristic search, which can exhibit exponential runtime in the presence of long traces or substantial deviations. This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP) defined on the reachabi