这个问题是NP-Hard http://en.wikipedia.org/wiki/NP-hard.
Define L={(G,n,m)|there is a legal seating for G in m×m matrix,(u,v) in E if u is friend of v}L 是这个问题作为语言的正式定义。
Proof:
我们将展示哈密顿量问题 ≤ (p) 2 路径 ≤ (p) 此问题分两步[哈密尔顿和下面定义的 2 路径]，因此我们得出结论这个问题是 NP-Hard。
(1) 我们将证明，在不两次使用任何顶点的情况下找到覆盖所有顶点的两条路径是 NP-Hard [让我们将这样的路径称为：2-path，并将此问题称为 2-path 问题]
减少自哈密顿路径问题 http://en.wikipedia.org/wiki/Hamiltonian_path:
input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u₀}.
正确性：
- 如果 G 具有哈密顿路径： v₁→v2→...→vn，则 G' 有 2 条路径：
v₁→v2→...→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₁ 位于 v2 旁边，则 v₁ v₁→v2 在路径中，因此
(v1,v2) 在 E 中，所以 v1,v2 是友元。
- 如果 (G,|V|+1,1) 是合法座位：[v₁,...,vk,buffer,vk+1,...,vn] ，G 中有一条 2 路，
v₁→...→vk, vk+1→...→vn
结论：该问题是 NP-Hard 问题，因此没有已知的多项式解。
指数解：您可能想使用回溯 http://en.wikipedia.org/wiki/Backtracking解决方案：基本上是：创建大小为|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)=infinity。当然可以进行优化，修剪这些情况。为了获得实际的坐姿，我们可以存储当前的最佳解决方案。
(*)可能有更好的解决方案，这只是一个简单的可能的解决方案，这个答案的主要目的是proving这个问题是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 http://en.wikipedia.org/wiki/Travelling_salesman_problem，这可以是solved http://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms in O(|V|^2 * 2^|V|)使用动态规划。
请注意，此解决方案 [使用 TSP] 适用于单排剧院，但它可能是为一般情况找到解决方案的一个很好的线索。
