Maximal Linear Arrangement is NP complete on Bipartite Graphs

@misc{das2026maximal,
  title = {{Maximal Linear Arrangement is NP complete on Bipartite Graphs}},
  author = {Aparna Das and Jonathan Needleman},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.12613},
  eprint = {2610.12613},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.12613},
}

TY  - UNPB
TI  - Maximal Linear Arrangement is NP complete on Bipartite Graphs
AU  - Aparna Das
AU  - Jonathan Needleman
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.12613
UR  - https://arxiv.org/abs/2610.12613
AB  - The linear arrangement of a simple graph G = (V,E) is a bijective labeling π of the vertices of G to the set {1, …, n}. The maximum linear arrangement (maxLA) problem is to determine whether G has a labeling such that the sum of labels across G's edges, ∑_uv ∈ E |π(u) − π(v)|, is at least a given value k. Minimum linear arrangement (minLA) is defined analogously. Both maxLA and minLA are known to be NP complete for general graphs. minLA has shown to be NP complete for bipartite graphs by Evans and Shiloah in 1975. It has been an open problem whether the same holds for maxLA. In this paper we prove that maxLA is NP complete for bipartite graphs.
ER  -