pith. sign in

arxiv: 2606.25719 · v1 · pith:2A4STOM4new · submitted 2026-06-24 · 💻 cs.AI

Position Spaces and Graphs

Rita-Nathalia Assaf , Tom Davot , Fr\'ed\'eric Lardeux , Fr\'ed\'eric Saubion This is my paper

Pith reviewed 2026-06-25 20:25 UTC · model grok-4.3

classification 💻 cs.AI
keywords position graphsstrict partial ordersgraph consistencyinduced subgraph isomorphismNP-completenessspatial constraintsqualitative reasoning
0
0 comments X

The pith

Position graphs using two strict partial orders keep induced subgraph isomorphism NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces position graphs to model relative positions of discrete tokens via two strict partial orders for horizontal and vertical alignment and precedence. These graphs are restricted by a chain condition and row/column compatibility requirements, which allow a characterization of when a position graph is consistent. The authors then examine the induced subgraph isomorphism problem as a model for structural pattern discovery and prove it remains NP-complete even on this restricted class. A sympathetic reader would care because the result shows that simplifying spatial constraints to partial orders and chains does not remove the computational hardness of pattern matching, while still providing a formal consistency layer independent of any particular data source.

Core claim

Position graphs are defined by two strict partial orders on a set of tokens that satisfy a chain condition together with row and column compatibility requirements; the paper gives necessary and sufficient conditions for consistency of such graphs and proves that the induced subgraph isomorphism problem on position graphs is NP-complete.

What carries the argument

Position graph: a pair of strict partial orders (horizontal and vertical) obeying a chain condition and row/column compatibility constraints that together represent spatial precedence and alignment of discrete tokens.

If this is right

  • Consistency of any position graph can be decided by checking the stated chain and compatibility conditions.
  • Structural pattern discovery in position-based data remains NP-hard even after the restrictions to partial orders and chains.
  • The framework supplies an algebraic consistency layer that is independent of any specific extraction or parsing technique.
  • Results apply directly to any discrete tokens whose positions are described by the two-order model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The retained NP-completeness implies that practical pattern search on position data will still require heuristics or restrictions beyond the graph model itself.
  • The same two-order representation could be tested on other domains that involve row-column layouts, such as table extraction or circuit placement.
  • If the chain condition is relaxed, the consistency characterization would no longer hold, but the hardness result might still apply to the broader class.

Load-bearing premise

All relevant position constraints in the domain can be captured exactly by two strict partial orders that obey the chain condition and the row/column compatibility requirements.

What would settle it

A polynomial-time algorithm that solves induced subgraph isomorphism on arbitrary position graphs would falsify the NP-completeness result.

Figures

Figures reproduced from arXiv: 2606.25719 by Fr\'ed\'eric Lardeux, Fr\'ed\'eric Saubion, Rita-Nathalia Assaf, Tom Davot.

Figure 1
Figure 1. Figure 1: Illustration of conditions satisfied by an alignment relation. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of inconsistent position spaces. Vertical alignments [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Position graph GP. h-cycle) (t1 = t, . . . , tk = t ′ , t) in GPΠ since there is an arc labelled h (resp. v) between t and t ′ . Moreover, if there is a v-cycle (resp. h-cycle) (t1 = t, . . . , tk−1 = t ′ , tk = t) in GPΠ, then there is a v-chain (resp. h-chain) (t1 = t, . . . , tk−1 = t ′ ) in Π. Hence, (T , <h, <v) does not contain a v-chain (resp. h-chain) if and only if GPΠ does not contain a v-cycle (… view at source ↗
Figure 4
Figure 4. Figure 4: Example of graphs produced by Construction 1 with input formula [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Example of a graph produced by Construction 2 with input for [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
read the original abstract

In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces position graphs, a representation using two strict partial orders (horizontal and vertical) subject to a chain condition and row/column compatibility requirements. It claims to characterize the consistency of such graphs via necessary and sufficient conditions and to prove that induced subgraph isomorphism remains NP-complete when restricted to this class of graphs. The work is motivated by document processing but emphasizes the underlying algebraic and complexity properties.

Significance. If the consistency characterization is correct and the NP-completeness reduction preserves the chain condition and compatibility constraints, the result supplies a formally grounded, restricted qualitative spatial framework whose complexity is pinned down precisely. This could support downstream algorithmic work on positional pattern matching in discrete token arrangements.

major comments (2)
  1. [computational complexity section] The section on computational complexity (following the consistency characterization): the claimed polynomial-time reduction from general induced subgraph isomorphism must be shown to produce only valid position graphs obeying the chain condition and row/column compatibility. If any constructed instance violates these extra constraints, the reduction establishes hardness only for a superclass, not for the restricted class stated in the abstract.
  2. [consistency characterization section] Consistency characterization section: the manuscript states that conditions ensuring consistency are established, yet provides no proof sketch, lemma statement, or verification that the stated conditions are both necessary and sufficient for graphs obeying the two partial orders plus chain/compatibility requirements. This is load-bearing for the subsequent complexity claim.
minor comments (1)
  1. [abstract] The abstract is dense and could more explicitly separate the consistency result from the complexity result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on the manuscript. We address each major comment below.

read point-by-point responses

  1. Referee: [computational complexity section] The section on computational complexity (following the consistency characterization): the claimed polynomial-time reduction from general induced subgraph isomorphism must be shown to produce only valid position graphs obeying the chain condition and row/column compatibility. If any constructed instance violates these extra constraints, the reduction establishes hardness only for a superclass, not for the restricted class stated in the abstract.

    Authors: We agree that the reduction must be shown to produce instances satisfying the chain condition and row/column compatibility to establish NP-completeness for position graphs specifically. The current manuscript describes the reduction but does not include an explicit verification that the constructed graphs obey these constraints. We will revise the computational complexity section to add a lemma or detailed argument proving that all instances generated by the reduction are valid position graphs. revision: yes

  2. Referee: [consistency characterization section] Consistency characterization section: the manuscript states that conditions ensuring consistency are established, yet provides no proof sketch, lemma statement, or verification that the stated conditions are both necessary and sufficient for graphs obeying the two partial orders plus chain/compatibility requirements. This is load-bearing for the subsequent complexity claim.

    Authors: The referee correctly identifies that the manuscript states the consistency conditions without providing a lemma, proof sketch, or verification of necessity and sufficiency under the full set of constraints. We will revise the consistency characterization section to include a formal lemma with a proof establishing that the conditions are necessary and sufficient for position graphs. revision: yes

Circularity Check

0 steps flagged

No circularity: new framework definitions yield independent consistency characterization and standard NP-completeness reduction

full rationale

The paper defines position graphs from two strict partial orders plus chain/compatibility constraints, then derives a consistency characterization directly from those definitions and proves NP-completeness of induced subgraph isomorphism via reduction to the restricted class. No equations reduce a claimed result to a fitted parameter or self-referential definition. No load-bearing self-citations appear. The derivation chain is self-contained against the stated axioms; the skeptic concern addresses reduction validity rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on the introduction of two new formal objects (position spaces and position graphs) together with domain assumptions about partial orders and an ad-hoc chain/compatibility restriction. No numeric parameters are fitted.

axioms (2)
  • domain assumption Relative positions of discrete tokens can be modeled by two strict partial orders (horizontal and vertical).
    Stated as the modeling choice that replaces general qualitative spatial calculi.
  • ad hoc to paper Position graphs obey a chain condition and compatibility requirements focused on rows and columns.
    Explicitly introduced to constrain the representation beyond general partial orders.
invented entities (2)
  • position spaces no independent evidence
    purpose: Formal basis for representing relative positions of tokens.
    Newly defined object on which the graph framework is built.
  • position graphs no independent evidence
    purpose: Graph-based reasoning structure derived from position spaces.
    Core new artifact whose consistency and complexity properties are analyzed.

pith-pipeline@v0.9.1-grok · 5687 in / 1395 out tokens · 24429 ms · 2026-06-25T20:25:35.974375+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 15 canonical work pages

  1. [1]

    , Lardeux , F

    barticle Saout , T. , Lardeux , F. , Saubion , F. : An overview of data extraction from invoices . IEEE Access 12 , 19872 -- 19886 ( 2024 ) 10.1109/ACCESS.2024.3360528 barticle

    work page doi:10.1109/access.2024.3360528 2024

  2. [2]

    A Framework for Formally Verifying Software Transactional Memory Algorithms

    bchapter Knight , S. , Palamidessi , C. , Panangaden , P. , Valencia , F.D. : Spatial and epistemic modalities in constraint-based process calculi . In: Koutny , M. , Ulidowski , I. (eds.) CONCUR 2012 -- Concurrency Theory -- 23rd International Conference, CONCUR 2012, Newcastle upon Tyne, UK, September 4--7, 2012. Proceedings . Lecture Notes in Computer ...

    work page doi:10.1007/978-3-642-32940-1 2012

  3. [3]

    , Cohn , A.G

    barticle Chen , J. , Cohn , A.G. , Liu , D. , Wang , S. , Ouyang , J. , Yu , Q. : A survey of qualitative spatial representations . Knowl. Eng. Rev. 30 ( 1 ), 106 -- 136 ( 2015 ) 10.1017/S0269888913000350 barticle

    work page doi:10.1017/s0269888913000350 2015

  4. [4]

    , Anderson , D.T

    bchapter Buck , A.R. , Anderson , D.T. , Keller , J.M. , Luke , R.H. , Scott , G. : A comparison of relative position descriptors for 3d objects . In: 2022 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) , pp. 1 -- 10 ( 2022 ). 10.1109/FUZZ-IEEE55066.2022.9882693 bchapter

    work page doi:10.1109/fuzz-ieee55066.2022.9882693 2022

  5. [5]

    : A new representation method of the relative position between objects in the image based on the histogram of position sensing forces

    barticle Tian , Z. : A new representation method of the relative position between objects in the image based on the histogram of position sensing forces . Scientific Reports 14 , 764 ( 2024 ) 10.1038/s41598-024-51396-x barticle

    work page doi:10.1038/s41598-024-51396-x 2024

  6. [6]

    , Cui , Z

    bchapter Randell , D.A. , Cui , Z. , Cohn , A.G. : A spatial logic based on regions and connection . In: Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning . KR'92 , pp. 165 -- 176 . Morgan Kaufmann Publishers Inc. , San Francisco, CA, USA ( 1992 ) bchapter

    1992

  7. [7]

    , Bennett , B

    barticle Cohn , A.G. , Bennett , B. , Gooday , J. , Gotts , N.M. : Qualitative spatial representation and reasoning with the region connection calculus . GeoInformatica 1 ( 3 ), 275 -- 316 ( 1997 ) 10.1023/A:1009712514511 barticle

    work page doi:10.1023/a:1009712514511 1997

  8. [8]

    , Nebel , B

    barticle Renz , J. , Nebel , B. : On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus . Artif. Intell. 108 ( 1-2 ), 69 -- 123 ( 1999 ) 10.1016/S0004-3702(99)00002-8 barticle

    work page doi:10.1016/s0004-3702(99)00002-8 1999

  9. [9]

    , Lagniez , J.-M

    bchapter Glorian , G. , Lagniez , J.-M. , Montmirail , V. , Sioutis , M. : An incremental SAT -based approach to reason efficiently on qualitative constraint networks . In: Hooker , J.N. (ed.) Principles and Practice of Constraint Programming -- 24th International Conference, CP 2018, Lille, France, August 27--31, 2018, Proceedings . Lecture Notes in Comp...

    work page doi:10.1007/978-3-319-98334-9 2018

  10. [10]

    , Lardeux , F

    bchapter Saout , T. , Lardeux , F. , Saubion , F. : A two-stage approach for tables extraction in invoices . In: 35th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2023, Atlanta, GA, USA, November 6-8, 2023 , pp. 10 -- 15 . IEEE , Los Alamitos, CA ( 2023 ) bchapter

    2023

  11. [11]

    : Über die Klassenzahl Abelscher Zahlkörper

    bbook Hasse , H. : Über die Klassenzahl Abelscher Zahlkörper . De Gruyter , Berlin, Boston ( 1952 ). 10.1515/9783112471388 bbook

    work page doi:10.1515/9783112471388 1952

  12. [12]

    , title =

    bchapter Cook , S.A. : The complexity of theorem-proving procedures . In: Proceedings of the Third Annual ACM Symposium on Theory of Computing . STOC '71 , pp. 151 -- 158 . Association for Computing Machinery , New York, NY, USA ( 1971 ). 10.1145/800157.805047 bchapter

    work page doi:10.1145/800157.805047 1971

  13. [13]

    : The complexity of comparability graph recognition and coloring

    barticle Golumbic , M.C. : The complexity of comparability graph recognition and coloring . Computing 18 ( 3 ), 199 -- 208 ( 1977 ) barticle

    1977

  14. [14]

    : Algorithmic Graph Theory and Perfect Graphs

    bbook Golumbic , M.C. : Algorithmic Graph Theory and Perfect Graphs . Academic Press , New York ( 1980 ). Classic reference on comparability graphs and transitive orientations bbook

    1980

  15. [15]

    : Combinatorics and Partially Ordered Sets: Dimension Theory

    bbook Trotter , W.T. : Combinatorics and Partially Ordered Sets: Dimension Theory . Johns Hopkins University Press , Baltimore ( 1992 ) bbook

    1992

  16. [16]

    : Combinatorics of Permutations

    bbook B \'o na , M. : Combinatorics of Permutations . Chapman & Hall/CRC , Boca Raton ( 2004 ) bbook

    2004

  17. [17]

    , Tardos , G

    barticle Marcus , A. , Tardos , G. : Excluded permutation matrices and the stanley--wilf conjecture . Journal of Combinatorial Theory, Series A 107 ( 1 ), 153 -- 160 ( 2004 ) barticle

    2004

  18. [18]

    , Prosser , P

    barticle McCreesh , C. , Prosser , P. , Solnon , C. , Trimble , J. : When subgraph isomorphism is really hard, and why this matters for graph databases . Journal of Artificial Intelligence Research 61 , 723 -- 759 ( 2018 ) barticle

    2018

  19. [19]

    , Yazici , A

    barticle Asiler , M. , Yazici , A. , George , R. : Hygraph: a subgraph isomorphism algorithm for efficiently querying big graph databases . J. Big Data 9 ( 1 ), 40 ( 2022 ) 10.1186/S40537-022-00589-0 barticle

    work page doi:10.1186/s40537-022-00589-0 2022

  20. [20]

    , Zhang , Z

    barticle Lu , Y. , Zhang , Z. , Zheng , W. , Zou , L. : Accelerating subgraph matching through fine-grained and powerful equivalences . Proc. VLDB Endow. 18 ( 11 ), 3896 -- 3909 ( 2025 ) 10.14778/3749646.3749662 barticle

    work page doi:10.14778/3749646.3749662 2025

  21. [21]

    , Prosser , P

    bchapter McCreesh , C. , Prosser , P. , Trimble , J. : The glasgow subgraph solver: Using constraint programming to tackle hard subgraph isomorphism problem variants . In: Gadducci , F. , Kehrer , T. (eds.) Graph Transformation -- 13th International Conference, ICGT 2020, Bergen, Norway, June 25--26, 2020, Proceedings . Lecture Notes in Computer Science ,...

    work page doi:10.1007/978-3-030-51372-6-19 2020

  22. [22]

    : Lad2025, A constraint-based solver for the subgraph isomorphism problem

    barticle Solnon , C. : Lad2025, A constraint-based solver for the subgraph isomorphism problem . Artif. Intell. 352 , 104474 ( 2026 ) 10.1016/J.ARTINT.2025.104474 barticle

    work page doi:10.1016/j.artint.2025.104474 2026

  23. [23]

    , Johnson , D.S

    bbook Garey , M.R. , Johnson , D.S. : Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , San Francisco ( 1979 ) bbook

    1979

  24. [24]

    : Qualitative spatial reasoning about distances and directions in geographic space

    barticle Frank , A.U. : Qualitative spatial reasoning about distances and directions in geographic space . J. Vis. Lang. Comput. 3 ( 4 ), 343 -- 371 ( 1992 ) 10.1016/1045-926X(92)90007-9 barticle

    work page doi:10.1016/1045-926x(92)90007-9 1992

  25. [25]

    , Joe , G

    bchapter Mukerjee , A. , Joe , G. : A qualitative model for space . In: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90) , pp. 721 -- 727 . AAAI Press , Menlo Park, CA ( 1990 ). https://aaai.org/papers/00721-aaai90-108-a-qualitative-model-for-space/ bchapter

    1990

  26. [26]

    , Li , S

    bchapter Liu , W. , Li , S. , Renz , J. : Combining RCC-8 with qualitative direction calculi: Algorithms and complexity . In: Boutilier , C. (ed.) IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 , pp. 854 -- 859 ( 2009 ). http://ijcai.org/Proceedings/09/Papers/146.p...

    2009

  27. [27]

    : A theory for qualitative spatial reasoning based on order relations

    bchapter R \" o hrig , R. : A theory for qualitative spatial reasoning based on order relations . In: Hayes - Roth , B. , Korf , R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 2 , pp. 1418 -- 1423 . AAAI Press / The MIT Press , Menlo Park, CA ( 1994 ). http://www.aaai....

    1994