Certified Directly\-Follows Before Case Correlation: Exact Local Certificates and Global Complexity under Joint Case and Order Uncertainty

Event-correlation methods reconstruct missing case identifiers before downstream process analysis, while uncertain-event and partial-order process-mining methods typically quantify temporal ambiguity inside already formed cases or traces. We study an earlier certification problem: which directly-follows statements are already forced, possible, or refutable when case membership is not selected and event order is only partially attested? After contracting trusted must-links, admissible case assignments are partitions compatible with attested cannot-links, while temporal completions are linear extensions of a trusted event partial order. We derive exact local MAY and MUST criteria for an event pair over the joint completion space and show that they are polynomially decidable after reachability preprocessing, with small explicit counter-witnesses. We then prove a sharp complexity separation: computing a globally tight maximum A->B directly-follows frequency over all admissible case partitions is NP-complete even under a fixed total order and highly restricted event structure. Moreover, summing local MAY pairs can overestimate the globally attainable frequency by an unbounded factor. A complementary interaction expansion shows that aggregate directly-follows targets can contain genuine higher-order interactions, so pairwise or triple linkage information is not generally complete. As a methodological safeguard, we state an exact factorization gate for correlated evidence uncertainty: joint evidence, completion, or target structures may be replaced by independent marginals only when exact factorization is certified. The intended contribution is therefore not a new correlation algorithm, but an attestation-first certification layer that separates locally exact conclusions from globally hard or model-dependent ambiguity before heuristic case correlation is promoted to evidence.