# A Fast Algorithm for Consistency Checking Partially Ordered Time

arXiv: https://arxiv.org/abs/2305.15917 · HTML: https://mlsanity.com/paper/2305.15917/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 35 references that are in the map.
- First posted on arXiv 25 May 2023.

## Builds on (most cited first, 1 of 1)

- [A Multivariate Complexity Analysis of Qualitative Reasoning Problems](https://mlsanity.com/paper/2209.15275/) (2022)

## Built on by (most cited first, 1 of 1)

- [Maximum Satisfiability of Simple Temporal Problems](https://mlsanity.com/paper/2607.23785/) (2026)

## Abstract (arXiv)

Partially ordered models of time occur naturally in applications where agents or processes cannot perfectly communicate with each other, and can be traced back to the seminal work of Lamport. In this paper we consider the problem of deciding if a (likely incomplete) description of a system of events is consistent, the network consistency problem for the point algebra of partially ordered time (POT). While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT except that it can be solved in O^*((0.368n)n) time by enumerating ordered partitions. We construct a much faster algorithm with a run-time bounded by O^*((0.26n)n). This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded toward a solution. While similar ideas have been explored earlier for related problems it turns out that the analysis for POT is non-trivial and requires significant new ideas.