Suppose you have $n$ people, numbered $0$ to $n-1$. We might as well suppose person $0$ stays put, and the others move around. So a "configuration" corresponds to a permutation of $1$ to $n-1$. Let $a_{i,j,c} = 1$ if $i$ and $j$ are seated next to each other in configuration $c$, $0$ if not. You can think of your problem as an integer linear programming problem:
$\eqalign{\text{minimize } & \sum_c x_c\cr \text{subject to } & \sum_c a_{i,j,c} x_c \ge 1 \ \text{for all } 0 \le i
The trouble is that there are a huge number of configurations ($9! = 362880$ in your example).
I tried a different approach: tabu search. In the cases I've tried it didn't take long to come up with an optimal solution. Here's my Maple program:
n:= 10; # number of guests m:= ceil((n-1)/2); # minimal number of rounds required scorer:= proc(L) # count number of introductions for an m-tuple of configurations nops(map(op,{seq([seq({L[i,j],L[i,j+1]},j=1..n-2), {0,L[i,1]},{0,L[i,n-1]}],i=1..m)})) end proc; move:= proc(i,j,k,L) # switch j'th and k'th positions in configuration i of m-tuple L local M; M:= L; M[i,j]:= L[i,k]; M[i,k]:= L[i,j]; M end proc; target:= n*(n-1)/2; # necessary number of introductions current:= [[1..(n-1)],seq(combinat[randperm](n-1),i=2..m)]; tabu:= [seq([2,i],i=1..7)]; # these items temporarily can't be switched currentscore:= scorer(current); bestyet:= current; bestscore:= scorer(bestyet); for iter from 1 to 1000 while bestscore < target do bestnewscore:= 0; for i from 2 to m do for j from 1 to n-2 do if member([i,j],tabu) then next fi; for k from j+1 to n-1 do if member([i,k],tabu) then next fi; newtry:= move(i,j,k,current); newscore:= scorer(newtry); if newscore > bestnewscore then bestnew:= newtry; bestnewscore:= newscore; ij:= [i,j]; ik:= [i,k]; fi od od od: if bestnewscore > bestscore then bestyet:= bestnew; bestscore:= bestnewscore; printf("Best yet at iteration %d: %d\n",iter, bestscore); fi; current:= bestnew; tabu:= [op(tabu[3..7]),ij,ik]; if iter mod 20 = 0 then printf("iteration %d, score %d\n",iter, bestnewscore) fi; od: if bestnewscore = target then printf("Optimal configuration ") else printf("Best configuration so far ") fi; printf("with score %d out of %d:\n",bestscore,target); print(bestyet);
For example, with n=15$ it took 312 iterations to come up with an optimal solution:
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], [5, 10, 3, 11, 13, 7, 9, 6, 14, 4, 12, 1, 8, 2], [11, 7, 10, 1, 5, 13, 2, 4, 8, 14, 9, 12, 3, 6], [10, 14, 3, 7, 4, 11, 2, 6, 8, 12, 5, 9, 1, 13], [3, 5, 7, 2, 14, 12, 6, 10, 8, 13, 4, 1, 11, 9], [8, 11, 14, 5, 2, 12, 10, 13, 3, 9, 4, 6, 1, 7], [4, 10, 2, 9, 13, 6, 11, 5, 8, 3, 1, 14, 7, 12]]
That is, there are 7 rounds; each row above lists the seating arrangement around the table starting to the right of person 0.