Half-Integrality, Odd-Cycle Certificates, and Weighted Reconstruction Costs in Finite Conflict Graphs: An ANTEFORMA 2.1–3.0 Reconstruction-Model Audit

We study finite target reconstruction through distinguishability conflicts and their representation as finite covering problems. Arbitrary finite covering incidences are realized explicitly by binary probes acting on disjoint two-hypothesis base-observation fibers. The graph-incidence subclass leads to bounded covering problems with heterogeneous edge demands, integer channel capacities, and weighted reconstruction costs. Using self-contained active-constraint arguments, we establish half-integrality of linear-programming vertices for integer data, integrality of all vertices under even edge demands, and structural certificates of fractional vertices based on unanchored active odd cycles and parity conditions. Exact rational computations and independently implemented finite audits illustrate the distinction between fractional polyhedral geometry, fractional optimal solutions, and positive integer–linear-programming optimality gaps. Explicit primal, dual, and integer certificates support reproducible verification of selected examples. The contribution is a unified reconstruction-model formulation, explicit structural certificates, and a reproducible computational audit. The underlying graph-polyhedral principles have substantial precedent in classical combinatorial optimization, particularly vertex-cover linear programming and half-integrality theory. No claim of historical priority for these classical results is made. The accompanying research package contains the LaTeX manuscript, Python 3 source code, mathematical audit reports, bibliographic notes, licensing information, and SHA-256 integrity checks. The programs use only the Python standard library and can be executed offline, including in Pydroid 3. This publication is a non-peer-reviewed mathematical preprint. External independent peer review and comprehensive verification of historical novelty remain outstanding. No empirical physical realization is claimed. Licensing: The manuscript and original documentation are distributed under Creative Commons Attribution 4.0 International (CC BY 4.0). The accompanying original Python source code is distributed under the MIT License. The respective license notices are included in the research archive. These licenses do not supersede the rights of third-party cited works. AI assistance was used in manuscript drafting, mathematical exposition, Python code preparation, computational verification, and bibliographic review. The human author retains responsibility for the mathematical definitions, results, source attribution, interpretation, and publication decision. AI-assisted auditing does not constitute independent external peer review.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24342384
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Half-Integrality, Odd-Cycle Certificates, and Weighted Reconstruction Costs in Finite Conflict Graphs: An ANTEFORMA 2.1–3.0 Reconstruction-Model Audit

Ivo Vajc
4 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Half-Integrality, Odd-Cycle Certificates, and Weighted Reconstruction Costs in Finite Conflict Graphs: An ANTEFORMA 2.1–3.0 Reconstruction-Model Audit

Ivo Vajc
preprint en

Abstract

We study finite target reconstruction through distinguishability conflicts and their representation as finite covering problems. Arbitrary finite covering incidences are realized explicitly by binary probes acting on disjoint two-hypothesis base-observation fibers. The graph-incidence subclass leads to bounded covering problems with heterogeneous edge demands, integer channel capacities, and weighted reconstruction costs. Using self-contained active-constraint arguments, we establish half-integrality of linear-programming vertices for integer data, integrality of all vertices under even edge demands, and structural certificates of fractional vertices based on unanchored active odd cycles and parity conditions. Exact rational computations and independently implemented finite audits illustrate the distinction between fractional polyhedral geometry, fractional optimal solutions, and positive integer–linear-programming optimality gaps. Explicit primal, dual, and integer certificates support reproducible verification of selected examples. The contribution is a unified reconstruction-model formulation, explicit structural certificates, and a reproducible computational audit. The underlying graph-polyhedral principles have substantial precedent in classical combinatorial optimization, particularly vertex-cover linear programming and half-integrality theory. No claim of historical priority for these classical results is made. The accompanying research package contains the LaTeX manuscript, Python 3 source code, mathematical audit reports, bibliographic notes, licensing information, and SHA-256 integrity checks. The programs use only the Python standard library and can be executed offline, including in Pydroid 3. This publication is a non-peer-reviewed mathematical preprint. External independent peer review and comprehensive verification of historical novelty remain outstanding. No empirical physical realization is claimed. Licensing: The manuscript and original documentation are distributed under Creative Commons Attribution 4.0 International (CC BY 4.0). The accompanying original Python source code is distributed under the MIT License. The respective license notices are included in the research archive. These licenses do not supersede the rights of third-party cited works. AI assistance was used in manuscript drafting, mathematical exposition, Python code preparation, computational verification, and bibliographic review. The human author retains responsibility for the mathematical definitions, results, source attribution, interpretation, and publication decision. AI-assisted auditing does not constitute independent external peer review.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon