You have been assigned the task of making seating arrangements for an event. You

Question

You have been assigned the task of making seating arrangements for an event. You are given a list L of guests, and a "knows-table" T such that, for each guest u small element L, T(u) is the list of guests that u knows. Design an algorithm that will make seating assignments that: (a) Minimizes the number of tables (each table can seat up to p people); (b) at each table there is a mix of some people who know each other and some who do not. (If you think you need to make an assumption about the number k of people who know each other at each table, you may do so.) Show that the algorithm is correct, state its complexity (with respect to what?), and show why

Explanation / Answer

This problem is 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 is a formal definition of this problem as a language.

Proof:
We will show Hamiltonian-Problem (p) 2-path (p) This-problem in 2 steps [Hamiltonian and 2-path defined below], and thus we conclude this problem is NP-Hard.

(1) We will show that finding two paths covering all vertices without using any vertex twice is NP-Hard [let's call such a path: 2-path and this problem as 2-path problem]
A reduction from Hamiltonian Path problem:

input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u}.
Correctness:

if G has Hamiltonian Path: vv...vn, then G' has 2-path: vv...vn,u
if G' has 2-path, since u is isolated from the rest vertices, there is a path: v...vn, which is Hamiltonian in G.
Thus: G has Hamiltonian path 1 G' has 2-path, and thus: 2-path problem is NP-Hard.

(2)We will now show that our problem [L] is also NP-Hard:
We will show a reduction from the 2-path problem, defined above.

input: a graph G=(V,E)
output: (G,|V|+1,1) [a long row with |V|+1 sits].
Correctness:

If G has 2-path, then we can seat the people, and use the 1 sit gap to use as a 'buffer' between the two paths, this will be a legal perfect seating since if v is sitting next to v, then v vv is in the path, and thus (v,v) is in E, so v,v are friends.
If (G,|V|+1,1) is legal seat:[v,...,vk,buffer,vk+1,...,vn] , there is a 2-path in G, v...vk, vk+1...vn
Conclusion: This problem is NP-Hard, so there is not known polynomial solution for it.

Exponential solution: You might want to use backtracking solution: which is basically: create all subsets of E with size |V|-2 or less, check which is best.

static best <- infinity
least_know(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_know(G,used + e)
in here we assume evaluate(used) gives the 'score' for this solution. if this solution is completely illegal [i.e. a vertex appear twice], evaluate(used)=infinity. an optimization can of course be made, trimming these cases. to get the actual sitting we can store the currently best solution.

(*)There are probably better solutions, this is just a simple possible solution to start with, the main aim in this answer is proving this problem is NP-Hard.

EDIT: simpler solution:
Create a graph G'=(V U { u } ,E U {(u,v),(v,u) | for each v in V}) [u is a junk vertex for the buffer] and a weight function for edges:

w((u,v)) = 1 u is friend of v
w((u,v)) = 2 u is known v
w((u0,v)) = w ((v,u0)) = 0
Now you got yourself a classic TSP, which can be solved in O(|V|^2 * 2^|V|) using dynamic programming.

thank you

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.