pith. sign in

arxiv: 2605.26505 · v1 · pith:FOR5JNR7new · submitted 2026-05-26 · 🧮 math.CO · cs.DM

A note on the exact partition polytope of Frieze and Teng

Krishna Narayanan , Tamon Stephen This is my paper

Pith reviewed 2026-06-29 17:35 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords exact partitionpolytopedegeneracyinteger linear programmingFrieze-Teng formulationcombinatorial optimization
0
0 comments X

The pith

The Frieze-Teng polytope for Exact Partition can be degenerate for some valid instances.

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

Frieze and Teng gave an integer linear programming formulation for the Exact Partition problem and claimed that its LP relaxation is always non-degenerate. This paper shows that this is not the case by constructing an instance that produces a degenerate polytope. It studies the conditions under which degeneracy occurs and provides details on one of the smallest such polytopes, as well as a related non-degenerate polytope for an equivalent problem. For applications in complexity theory, a simple preprocessing step can avoid these degenerate cases.

Core claim

Contrary to the claim by Frieze and Teng, there exist instances of the Exact Partition problem for which the polytope defined by their inequalities is degenerate. The paper exhibits such an instance, describes conditions for degeneracy, and gives explicit details of a small degenerate Frieze-Teng polytope along with a non-degenerate one for an equivalent instance. These degenerate polytopes can be avoided by preprocessing for the purposes of existing complexity results.

What carries the argument

The Frieze-Teng polytope, defined by the inequalities in the Frieze-Teng integer linear programming formulation of Exact Partition, which is shown to be degenerate in some cases.

If this is right

  • Degeneracy can occur in the LP relaxation of the Exact Partition formulation.
  • Conditions for when degeneracy occurs can be identified.
  • Equivalent instances can produce non-degenerate polytopes instead.
  • A simple preprocessing step suffices to avoid degenerate cases in complexity analyses.

Where Pith is reading between the lines

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

  • Users of the formulation in algorithms may encounter numerical or pivoting issues on degenerate instances.
  • The choice of specific numbers in an Exact Partition instance can change the geometric properties of the relaxation.
  • Similar degeneracy phenomena might appear in other partition-related polytope formulations.

Load-bearing premise

The constructed instance is a valid input to the Exact Partition problem and the associated polytope is exactly the one defined by the Frieze-Teng inequalities.

What would settle it

Verification that the presented instance does not produce a degenerate polytope, or is not a valid input, would falsify the central claim.

Figures

Figures reproduced from arXiv: 2605.26505 by Krishna Narayanan, Tamon Stephen.

Figure 2
Figure 2. Figure 2: 3.2. Conditions for degeneracy in PR In this section, we briefly elaborate conditions for PR to have degenerate vertices. The first, of course, is that si = smax 2 for some i ∈ [2m]. We note that the example provided is for a polytope with an exact partition, and that the degenerate vertex contains m ones, corresponding to this exact partition. In fact, this turns out to be required for such a degenerate v… view at source ↗
Figure 1
Figure 1. Figure 1: Schlegel diagram of PR for the {3, 3, 4, 2} instance on the outer facet x1 = 0 (facet edges in black). 4 5 15 16 23 3 6 7 8 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Schlegel diagram of PR for the {2, 2, 3, 1} instance on the outer facet x1 = 0 (facet edges in black). 5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

In 1994, Frieze and Teng proposed an integer linear programming formulation of the NP-Complete Exact Partition problem, whose LP-relaxation they claimed was non-degenerate. Contrary to their claim, we show how an instance of Exact Partition can produce a degenerate polytope, and study conditions for which this can happen. We then give details of one of the smallest such degenerate Frieze-Teng polytopes, along with a closely related non-degenerate Frieze-Teng polytope that encodes an equivalent problem. We note that for the purposes of the complexity results in the literature that use their formulation, these degenerate polytopes can be avoided via a simple preprocessing step.

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

0 major / 1 minor

Summary. The manuscript constructs an explicit instance of the Exact Partition problem whose Frieze-Teng polytope is degenerate, contrary to the 1994 claim that the LP relaxation is always non-degenerate. It identifies conditions under which degeneracy arises, supplies coordinates and inequality data for one of the smallest degenerate polytopes together with a closely related non-degenerate polytope for an equivalent instance, and observes that a simple preprocessing step removes the degeneracy for downstream complexity arguments.

Significance. If the explicit construction is correct, the note supplies a concrete, checkable counter-example that corrects an inaccuracy in the literature on polyhedral formulations of NP-complete problems. The paired degenerate/non-degenerate examples and the preprocessing observation are directly usable by researchers who rely on the Frieze-Teng formulation for complexity results.

minor comments (1)
  1. The abstract states that 'details of one of the smallest such degenerate Frieze-Teng polytopes' are given; the main text should explicitly label the section or subsection containing the vertex/facet list and the numerical verification that the polytope is degenerate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; explicit counter-example construction

full rationale

The paper's central result is an explicit, checkable counter-example instance of Exact Partition together with direct verification that the associated Frieze-Teng polytope is degenerate. This construction is performed from the original problem definition and inequality system; no step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional renaming. The preprocessing observation is likewise a direct observation on the input instance rather than a derived claim. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of polytope degeneracy and on the exact inequality system published by Frieze and Teng; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption The Frieze-Teng inequality system is a valid integer programming formulation of Exact Partition.
    Invoked in abstract paragraph 1 when referring to the 1994 formulation.
  • standard math Degeneracy is defined by the existence of multiple bases for the same vertex in the LP relaxation.
    Standard linear-programming terminology used without re-derivation.

pith-pipeline@v0.9.1-grok · 5635 in / 1263 out tokens · 37231 ms · 2026-06-29T17:35:49.795021+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

7 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    A. M. Frieze, S.-H. Teng, On the complex- ity of computing the diameter of a polytope, Comput. Complexity 4 (3) (1994) 207–219. doi:10.1007/BF01206636

    work page doi:10.1007/bf01206636 1994

  2. [2]

    Narayanan, T

    K. Narayanan, T. Stephen, The hardness of monotone eccentricity on polytopes, in: N. Misra, A. Pandey (Eds.), Algorithms and Discrete Applied Mathematics, Springer Nature Switzerland, Cham, 2026, pp. 365–377

    2026

  3. [3]

    R. M. Karp, Reducibility among combinatorial problems, in: Complexity of computer compu- tations(Proc.Sympos., IBMThomasJ.Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, Plenum, New York-London, 1972, pp. 85–103

    1972

  4. [4]

    Korte, R

    B. Korte, R. Schrader, On the existence of fast approximation schemes, in: Nonlinear program- ming, 4 (Madison, Wis., 1980), Academic Press, New York-London, 1981, pp. 415–437

    1980

  5. [5]

    A. E. Black, R. Steiner, Finding short paths on simple polytopes (2026). arXiv:2603.05482. URLhttps://arxiv.org/abs/2603.05482

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  6. [6]

    Narayanan, The complexity of monotone shortest paths on simple polytopes, M.Sc

    K. Narayanan, The complexity of monotone shortest paths on simple polytopes, M.Sc. The- sis, Simon Fraser University (2025)

    2025

  7. [7]

    Gawrilow, M

    E. Gawrilow, M. Joswig, polymake: a framework for analyzing convex polytopes, in: Polytopes—combinatorics and computation (Oberwolfach, 1997), Vol. 29 of DMV Sem., Birkhäuser, Basel, 2000, pp. 43–73. 7

    1997