Position Spaces and Graphs: Position graphs, NP-complete result

Rita-Nathalia Assaf, Tom Davot, Frédéric Lardeux and Frédéric Saubion submitted Position Spaces and Graphs to arXiv on 24 Jun 2026 as arXiv:2606.25719, introducing a graph-based reasoning framework called position graphs. The paper formalizes position spaces, delivers a theoretical account of consistency for those graphs, and proves that structural pattern discovery, cast as induced subgraph isomorphism, remains NP-complete even within this restricted class.

How do position graphs model layout?

Position graphs model relative placement by using two strict partial orders that represent horizontal and vertical alignment and precedence. These two orders encode the positions of discrete tokens across rows and columns, rather than allowing arbitrary qualitative spatial relations. The framework imposes a chain condition and compatibility requirements that focus on rows and columns, constraining which relative positions are representable compared with general qualitative spatial calculi.

The paper frames these orders as the core algebraic objects of a position space and builds a graph representation on top of them. The authors then provide a characterization of graph consistency, followed by explicit conditions to ensure a position graph satisfies that consistency criterion.

What did the paper prove about complexity and pattern discovery?

The authors model structural pattern discovery as the induced subgraph isomorphism problem and demonstrate that the problem remains NP-complete even within the restricted class of position graphs. That NP-completeness result is central: despite the chain condition and the row/column compatibility constraints, induced subgraph matching does not become tractable in the general case under this representation.

Alongside the complexity result, the paper develops a comprehensive theoretical analysis of the representation itself, establishing the algebraic consistency of position-based constraints and giving conditions that guarantee a position graph is consistent. Those consistency results are presented before the complexity analysis, forming the formal logical layer the authors aim to isolate.

Why it matters

The paper extracts a purely mathematical layer from layout problems: position graphs formalize alignment and precedence with two partial orders, and the authors prove that the natural structural search problem over those graphs is NP-complete. That combination matters because the work was motivated by document processing, and it separates the logical constraints from any particular data extraction method. As a result, the findings set clear theoretical limits for algorithm designers who try to discover structural patterns purely from positional relations.

What to watch

Watch whether position graphs are adopted as a formal intermediate representation in document processing pipelines, and whether subsequent work produces practical algorithms or heuristics that can handle induced subgraph isomorphism in real layouts despite the NP-completeness shown in this paper. Also look for follow-up papers that apply the paper's consistency conditions to concrete extraction systems or that identify subclasses of position graphs with lower complexity.

References and provenance

The details above are drawn from the arXiv listing for Position Spaces and Graphs by Rita-Nathalia Assaf, Tom Davot, Frédéric Lardeux and Frédéric Saubion, submitted 24 Jun 2026, arXiv:2606.25719, subject Artificial Intelligence (cs.AI). The paper presents the formal framework, its consistency characterization, and the complexity proof about induced subgraph isomorphism remaining NP-complete within position graphs.