Maximal Linear Arrangement is NP complete on Bipartite Graphs

Abstract

The linear arrangement of a simple graph $G=(V,E)$ is a bijective labeling $\pi$ of the vertices of $G$ to the set $\{1,\dots ,n\}$. The maximum linear arrangement ($\text{maxLA}$) problem is to determine whether $G$ has a labeling such that the sum of labels across $G$'s edges, ${\sum }_{uv\in E}|\pi (u)-\pi (v)|$, is at least a given value $k$. Minimum linear arrangement ($\text{minLA}$) is defined analogously. Both $\text{maxLA}$ and $\text{minLA}$ are known to be NP complete for general graphs. $\text{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 $\text{maxLA}$. In this paper we prove that $\text{maxLA}$ is NP complete for bipartite graphs.

11 pages