NP-Hardness
Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or above some $k$?
The question "is there some way to assign seating positions to professors such that the total score obtained is greater than or equal to $\vert V_1 \vert + \vert V_2 \vert$" is NP-Complete, as it is only possible to do this if a hamiltonian path exists in both graphs.
Approximation algorithm ideas
NP-Hardness just guarantees that a problem can't always be solved exactly unless $P=NP$, however, it doesn't tell us anything about how difficult it is to approximate. Here is one idea I had, it's incomplete, but is at least something to get you started.
For simplicity, I will now consider the problem where there is a single circle of chairs, and we are trying to place professors in the same way you require. We will also restrict all preferences to be greater than or equal to 0. This can most likely be extended to your problem but I haven't got around to that yet, so I will update this problem once that is accomplished, or you can do this yourself.
With this "roundtable" problem, it turns out there is an algorithm I found that is guaranteed to find a solution that is no less than 8 times the optimal solution.
This algorithm does the following:
- Place each person randomly around the table.
- Consider a pair of people (any will do), and see if swapping them will increase the total score. If so, swap them.
- Repeat until no swap will increase your total score.
This is guaranteed to halt in polynomial time because each swap strictly increases the total score (I think? Still a little fuzzy about this part but I'm fairly sure that is true and will formalize it in a bit).
How good does this algorithm do? Well, call $Opt$ the optimal ordering of professors, and $Val$ the ordering of professors that this algorithm gives when it is done.
Now, consider any set of edges $(a, x)$, $(x, b)$, $(c, y)$, $(y, d)$ in your graph, where $a, x, b, c, y, d$ are professors. We will denote these edges $(a,x,b)$ and $(c, y, d)$ since by definition given any arrangement of professors they are next to each other.
We know that, if $y$ and $x$ could be swapped our algorithm would have done so. Call $\mid (a, x, b)\mid$ the score of edge $(a, x)$ plus the score of edge $(x, b)$. Then, if $(a, y, b)$ and $(c, x, d)$ are in val, we know
$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)|$$
Because either our algorithm swapped $x$ with $y$, or there was equal score regardless of the swap, in which case we have
$$|(a, y, b)| + |(c, x, d)| = |(a, x, b)| + |(c, y, d)|$$
Note that we technically also know
$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)| \geq |(c, y)|$$
Which is true because $|(a, x, b)| + |(c, y, d)|$ contains $|(c, y)|$ in it. Now we can look at the terms on both ends, and this gives us
$$|(a, y, b)| + |(c, x, d)| \geq |(c, y)|$$
Which holds for all edges $(c, y)$. Note that given any $(c, y)$, there is only one such pair of $(a, y, b)$ and $(c, x, d)$, because the positions $c$ and $y$ are fixed.
We know that the value of $Opt$ is equal to the sum of all it's edges $(v_1, v_2)$, $(v_2, v_3)$, ..., $(v_{n-1}, v_n)$, $v_n, v_1)$ (where $v_i$ is some professor), so for each of these, we get a single inequality. Consider the edge $(a, y)$. $|(a, y)|$ will only appear in an inequality if $a$, $y$, or the professor before $a$ is contained in the edge in Opt. Thus, worst case $(a, y)$ is counted 8 times, because each variable can be in at most two edges, by definition.
If we sum all of the edges on both sides, we get
$$8*Val\geq Opt$$
Thus
$$(8 \geq \frac{Opt}{Val})$$
which is a factor 8 approximation, as desired.