Jacek on things

Here's the old ancient wedding table problem that each man inevitably has to solve on his way to honeymoon. Research on the topic shows that some philosophers simplify this problem to set partitioning problem (not sure if they were on any wedding, or are they just dinning philosophers). Whereas others assign the problem to the social nature of participants. But I guess that for all my readers it's obvious that this is strictly mathematical subject and should be analysed from the algorithms perspective. Problem statement: Newlyweds are holding a party of n guests, where 2m of them comes in couples and the rest comes single. There's one long table with n chairs, split equally on both sides and each guest needs to have a chair assigned. Each couple has to together. Guests sitting next to each other, or on the opposite sides of the table are in talking range. There's a graph G(V, E), where each vertex represents a couple or single guest and each edge represents an acquai