同じ席に座れる関係を無向グラフ$G$で表すことにすると、可能な席数を求める問題は$G$をいくつかのクリークに分割する問題と解釈できる。したがって、この問題は最小クリーク被覆問題そのものなので、補グラフの彩色数を求めればよい。
彩色数を求める$O(2^nn)$アルゴリズム:
https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html
https://codeforces.com/blog/entry/57496
https://www.slideshare.net/wata_orz/ss-12131479
