这个问题是
NP-Hard的。定义
L={(G,n,m)|在m×m矩阵中有一个合法的G座位,(u,v)∈E，如果u是v的朋友} L是该问题的正式语言定义。
证明:
我们将用2步骤展示
哈密顿路径问题 ≤ (p) 2路径问题 ≤ (p) 这个问题 [哈密顿路径和2路径的定义如下]，从而我们得出结论，这个问题是NP-Hard的。
(1) 我们将展示找到两条覆盖所有顶点的路径，而不使用任何顶点两次是NP-Hard的[让我们称这样的路径为：2-path问题]
从
哈密顿路径问题进行约简：
input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u₀}.
正确性：
- 如果G有哈密顿路径：v₁→v₂→...→vn，则G'有2路径：
v₁→v₂→...→vn，u₀
- 如果G'有2路径，则由于u₀与其余顶点隔离，存在一条路径：v₁→...→vn，在G中是哈密顿路径。
因此：G具有哈密顿路径1 ⇔ G'具有2路径，因此：2路径问题是NP-Hard。
(2)我们现在将展示[L]问题也是NP-Hard的：
我们将从上面定义的2路径问题进行归约。
input: a graph G=(V,E)
output: (G,|V|+1,1) [a long row with |V|+1 sits].
正确性：
- 如果G有2路径，那么我们可以安排人员，并使用1个座位间隙作为两条路径之间的“缓冲区”，这将是合法的完美座位，因为如果v₁坐在v₂旁边，则v₁ v₁→v₂在路径中，因此(v₁,v₂)在E中，所以v₁，v₂是朋友。
- 如果(G，|V|+1,1)是合法的座位：[v₁，...，vk，buffer，vk+1，...，vn]，则G中存在2路径，v₁→...→vk，vk+1→...→vn
结论：该问题是NP-Hard问题，因此没有已知的多项式解决方案。
指数解决方案：
您可能想使用回溯解决方案：基本上是：创建大小为|V|-2或更小的所有E子集，检查哪个最好。
static best <- infinity
least_enemies(G,used):
if |used| <= |V|-2:
val <- evaluate(used)
best <- min(best,val)
if |used| == |V|-2:
return
for each edge e in E-used: //E without used
least_enemies(G,used + e)
在这里，我们假设evaluate(used)给出了此解决方案的“分数”。如果此解决方案完全非法[即一个顶点出现两次]，则evaluate(used)=infinity。当然可以进行优化，修剪这些情况。为了获得实际的解决方案，我们可以存储当前最佳解决方案。
(*)可能有更好的解决方案，这只是一个简单的可能的解决方案，本答案的主要目的是证明这个问题是NP-Hard。
编辑：更简单的解决方案：
创建一个图G'=(V U { u₀ } ,E U {(u₀,v),(v,u₀) | for each v in V}) [u₀对于缓冲区是一个垃圾顶点]和边的权重函数：
w((u,v)) = 1 u is friend of v
w((u,v)) = 2 u is an enemy v
w((u0,v)) = w ((v,u0)) = 0
现在您已经拥有一种经典的
TSP，可以使用动态规划在
O(|V|^2 * 2^|V|)中进行
求解。请注意，这种使用TSP的解决方案仅适用于单行剧院，但可能是解决通用情况的良好线索。
