Metraipolis › archive › dc_ec45e06f4b8f

Two-Colour Zig-Zag Numberlink on Rectangles: A Forbidden-Pattern Characterization, a Constructive Polynomial-Time Algorithm, and a Lean Verification — arXiv:2610.37691

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.37691
License (as archived)
CC0-1.0
Archived
2026-11-01T02:26:43.799Z
SHA-256 of the archived text
a3e7886d4b64f184e9e53c73bf9203615999006a1de85eff42bfa37d58b1471a
Stable URL of this page
https://metraipolis.com/documento/dc_ec45e06f4b8f

How to cite

Two-Colour Zig-Zag Numberlink on Rectangles: A Forbidden-Pattern Characterization, a Constructive Polynomial-Time Algorithm, and a Lean Verification — arXiv:2610.37691 — arXiv (en), https://arxiv.org/abs/2610.37691 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ec45e06f4b8f (Metraipolis archive dc_ec45e06f4b8f, sha256 a3e7886d4b64f184e9e53c73bf9203615999006a1de85eff42bfa37d58b1471a)
BibTeX
@misc{dcec45e06f4b8f,
  title = {Two-Colour Zig-Zag Numberlink on Rectangles: A Forbidden-Pattern Characterization, a Constructive Polynomial-Time Algorithm, and a Lean Verification — arXiv:2610.37691},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.37691},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ec45e06f4b8f; sha256 a3e7886d4b64f184e9e53c73bf9203615999006a1de85eff42bfa37d58b1471a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.37691. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In Zig-Zag Numberlink, pairs of endpoints in a grid must be joined by vertex-disjoint paths that together visit every cell. The problem is NP-complete when the number of pairs is un- bounded (Adcock et al.). For a single pair it is the Hamiltonian path problem in rectangular grid graphs, solved by Itai, Papadimitriou and Szwarcfiter. Two pairs on a rectangle form the paired 2-disjoint path cover problem. We settle the case of two pairs on rectangles with the endpoints anywhere in the grid. If both sides of the rectangle are at least 11, an instance is solvable if and only if no entry of a finite catalogue of forbidden patterns occurs. The catalogue consists of a parity condition, an alternation condition on the border, a handful of local corner and edge patterns, 65 listed corner configurations, and a rule that propagates forced routes out of the corners before testing alternation. If a side is at most 10, a frontier dynamic programming algorithm decides the instance in time linear in the long side. The characterization is construc- tive. Solutions are built by deleting empty lines, splitting the rectangle by straight cuts, and splicing the pieces back together, in time O((R+C) RC). Both directions of the characterization and the correctness of the dynamic programming algorithm are verified in Lean 4. The finite case analyses, which are window certificates for the corner configurations and a check of all irreducible instances with sides 11-22, are carried out by the Lean compiler via native decide. We describe the algorithm, the catalogue, the proof structure, the compromises made in the formalization, and implementations in Python, JavaScript and C that produce identical output.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.37691 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:12:44.225Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).