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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The linear extension diameter is NP-complete for posets of width 4

Hugo Jiménez‐Hernández, Erik-Josué Moreno-Mejía
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

The linear extension diameter is NP-complete for posets of width 4

Hugo Jiménez‐Hernández, Erik-Josué Moreno-Mejía
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Autonomous University of Queretaro (MX)
Advanced Graph Theory Research
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