Maximal Linear Arrangement is NP complete on Bipartite Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.12613
curl -X POST /api/v1/records/arxiv/2610.12613/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.12613/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'