The linear extension diameter is NP-complete for posets of width 4
The linear extension diameter led(P) of a finite poset P is the largest Kendall tau distance between two linear extensions of P. Brightwell and Massow proved that computing led(P) is NP-complete in general and polynomial for posets of width 3, and asked whether it is polynomial for every fixed width, or even for width 4. We show that it is NP-complete for posets of width 4, hence for every fixed width w ≥ 4. Together with their algorithm this gives an exact dichotomy: for fixed width the problem is polynomial if and only if the width is at most 3, unless P = NP. Since the farthest linear extension from a given one can be found in polynomial time for every fixed width, the hardness lies in the choice of the pair. The reduction is from independent set in planar graphs: two staggered ladders with heavy spines carry unboundedly many bits inside four chains, and light gadgets in the same chains add couplings, fields and cuts, so that the poset simulates a planar Ising model with a field. We also give a shorter width-5 construction that encodes MAX-CUT directly. Finally, answering a second question of Massow, we show that deciding led(P) ≥ k has a kernel with fewer than 2k elements and is therefore fixed-parameter tractable in k. Preprint. Submitted to SIAM Journal on Discrete Mathematics.
Authors
- Hugo Jiménez‐Hernández (ORCID: https://orcid.org/0000-0003-0827-6645)
- Erik-Josué Moreno-Mejía (ORCID: https://orcid.org/0009-0005-2461-9275)
Institutions
- Autonomous University of Queretaro (MX)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24209872
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint