{"id":"arxiv/2610.12613","url":"https://arxiv.org/abs/2610.12613","tags":["cs.DM","math.CO"],"score":0,"title":"Maximal Linear Arrangement is NP complete on Bipartite Graphs","domain":"cs.DM","source":"arxiv","authors":["Aparna Das","Jonathan Needleman"],"reviews":0,"subject":"cs.DM","summary":"The linear arrangement of a simple graph $G = (V,E)$ is a bijective labeling $π$ of the vertices of $G$ to the set $\\{1, \\ldots, n\\}$. The maximum linear arrangement ($\\texttt{maxLA}$) problem is to determine whether $G$ has a labeling such that the sum of labels across $G$'s edges, $\\sum_{uv \\in E} |π(u) - π(v)|$, is at least a given value $k$. Minimum linear arrangement ($\\texttt{minLA}$) is defined analogously. Both $\\texttt{maxLA}$ and $\\texttt{minLA}$ are known to be NP complete for general graphs. $\\texttt{minLA}$ has shown to be NP complete for bipartite graphs by Evans and Shiloah in…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-08","reactions":{}}