The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.research

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: restaurant seating problem
Replies: 1   Last Post: Jul 18, 2011 8:21 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ralph Boland

Posts: 2
Registered: 7/21/09
restaurant seating problem
Posted: Jul 17, 2011 10:57 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I would like to know the status of the following problem in terms of
whether or not there a polynomially bounded time solution.
Actually this is a family of problems, one for each value of  s
defined below.

A restaurant wishes to use as few tables as possible to seat a group
of  n  people.
Some pairs of people refuse to be seated together so to seat k people
at a table
requires that the graph of people willing to sit together implies the
k people form a clique.
A table is considered used if at least one person sits at the table.
It is not a requirement that each used table be filled.
Each table in the restaurant seats at most some constant number  s

What is the complexity of finding a solution for this problem for a
given value  s.

Note that if each table seats 2 people (s=2) then the problem is
reducible to
maximum matching and thus is solvable in polynomial time.

I have no doubt that for sufficiently large  s  the decision version
of this problem is NP-Complete.
But what is the smallest value of  s  for which  NP-Completeness

For  s = 3  I have ideas that might (but probably not at this early
lead to a polynomially bounded solution.
For  s >= 4  I have no insights at all.

Ideas welcome.
References welcome.
Pointing me to other groups more appropriate for this question

Finally, are there practical applications to this problem, especially
for the case of  s = 3 since I will
continue to explore a polynomially bounded solution for this case.

If you want to email me directly, my email is


Ralph Boland

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.