# Seating couples with fewest swaps

::: {.problem #problem-couples-seating-swaps title="Seating couples with fewest swaps"}
Let $n$ distinct people occupy $n$ seats arranged in a cycle, and let $2k$ of them form $k$ couples, with $k$ part of the input. A swap exchanges the occupants of any two seats. Find a shortest sequence of swaps after which the two members of every couple occupy adjacent seats.
:::

::: {.lemma #lem:fixed-target-couple-distance title="Distance to a fixed target"}
Let $P$ and $Q$ be size-$k$ matchings on the same labeled vertex set. Color the edges of $P$ red and the edges of $Q$ blue, retaining both colored copies of a common edge as an alternating $2$-cycle. Let $c(P,Q)$ be the number of alternating cycle components of $P\cup Q$, and let $q(P,Q)$ be the number of alternating path components with one more red edge than blue edge. The minimum number of vertex transpositions mapping $P$ to $Q$ is
$$
d(P,Q)=k-c(P,Q)+q(P,Q).
$$
An ordered list of exactly $d(P,Q)$ transpositions can be produced in linear time.
:::

::: {.proof}
For a size-$k$ matching $S$, define $F(S):=c(S,Q)-q(S,Q)$. We first prove that
$$
|F(tS)-F(S)|\le1
\tag{L1}
$$
for every vertex transposition $t=(x\,y)$.

If neither $x$ nor $y$ is incident with a red edge, or if they are the two endpoints of the same red edge, the red matching does not change. Suppose first that $x,y$ have distinct red mates $a,b$. The move replaces $\{a,x\},\{b,y\}$ by $\{a,y\},\{b,x\}$. Delete the two old red edges and call $a,x,b,y$ the ports. Every component meeting a port is a path joining two ports, called a link, a path joining one port to an ordinary endpoint, called a tail, or an isolated port, treated as a zero-length tail. The links form a partial matching $\mu$ on the four ports. Call a tail red-ended if its ordinary endpoint is incident only with a red edge and blue-ended if that endpoint is incident only with a blue edge, and treat an isolated port as red-ended.

Collapse every link and tail, and let $\rho$ be either the old or new perfect matching of the four ports. If two links remain, the affected score is $2$ when $\rho=\mu$ and $1$ otherwise. If one link and two tails with labels $\alpha,\beta$ remain, the score is
$$
\begin{cases}
1-\mathbf 1[\alpha,\beta\text{ are red-ended}],&\text{if $\rho$ contains the link},\\
-\mathbf 1[\alpha,\beta\text{ are red-ended}],&\text{otherwise}.
\end{cases}
\tag{L2}
$$
If no link remains, the score is the negative of the number of red-ended tail pairs joined by $\rho$. The first two cases change by at most one between the old and new pairings. In the last case, two perfect matchings of four tails have numbers of red-ended pairs differing by at most one. This proves (L1) when both transposed vertices are red-matched.

Suppose next that $x$ has red mate $a$ and $y$ is red-unmatched. The move replaces $\{a,x\}$ by $\{a,y\}$. Delete $\{a,x\}$, leaving the three ports $a,x,y$. If there is one link, the affected scores are

| link | old score | new score |
|---|---:|---:|
| $a$--$x$ | $1$ | $0$ |
| $a$--$y$ | $0$ | $1$ |
| $x$--$y$ | $0$ | $0$ |

If there is no link, label the three tails as above. Leaving one port red-unmatched contributes no negative score because it is isolated or is a blue-only endpoint. The old and new scores are
$$
-\mathbf 1[t_a,t_x\text{ are red-ended}]\qquad\text{and}\qquad-\mathbf 1[t_a,t_y\text{ are red-ended}],
\tag{L3}
$$
which differ by at most one. The case in which only $y$ is red-matched is symmetric, so (L1) holds for every transposition.

For any sequence $P=P_0,P_1,\ldots,P_m=Q$, equation (L1) and $F(Q)=k$ give
$$
m\ge F(Q)-F(P)=k-c(P,Q)+q(P,Q).
\tag{L4}
$$

It remains to attain the bound. For distinct vertices $z_0,\ldots,z_t$, the ordered transpositions
$$
(z_0\,z_1),(z_0\,z_2),\ldots,(z_0\,z_t)
\tag{L5}
$$
compose to the cycle $(z_0\,z_1\,\cdots\,z_t)$.

For an alternating cycle with $a$ red edges, index
$$
P_i=\{u_i,v_i\},\qquad Q_i=\{v_i,u_{i+1}\}\qquad(1\le i\le a),
\tag{L6}
$$
where $u_{a+1}=u_1$. The ordered list
$$
(u_1\,u_2),(u_1\,u_3),\ldots,(u_1\,u_a)
\tag{L7}
$$
maps every $P_i$ to $Q_i$ and has length $a-1$.

For a balanced alternating path with $a$ red and $a$ blue edges, use the same indexing for $1\le i\le a$, where $u_{a+1}=z$ is the red-unmatched endpoint. The list
$$
(u_1\,u_2),\ldots,(u_1\,u_a),(u_1\,z)
\tag{L8}
$$
maps its red edges to its blue edges and has length $a$.

The numbers of red-heavy and blue-heavy paths are equal because the sum, over all components, of the number of red edges minus the number of blue edges is $|P|-|Q|=0$. Pair these paths arbitrarily. Index a red-heavy path with $a$ red edges by
$$
P_i=\{u_i,v_i\}\ (1\le i\le a),\qquad Q_i=\{v_i,u_{i+1}\}\ (1\le i<a),
\tag{L9}
$$
and index its paired blue-heavy path with $b$ blue edges by
$$
Q'_j=\{w_j,z_j\}\ (1\le j\le b),\qquad P'_j=\{z_j,w_{j+1}\}\ (1\le j<b).
\tag{L10}
$$
Output
$$
(u_1\,u_2),\ldots,(u_1\,u_a),(u_1\,w_1)
\tag{L11}
$$
followed by
$$
(v_a\,z_1),(v_a\,z_2),\ldots,(v_a\,z_b).
\tag{L12}
$$
The two composite cycles are $(u_1\,u_2\,\cdots\,u_a\,w_1)$ and $(v_a\,z_1\,\cdots\,z_b)$. They map $P_i$ to $Q_i$ for $i<a$, map $P_a$ to $Q'_1$, and map $P'_j$ to $Q'_{j+1}$ for $j<b$. The paired paths therefore take $a+b$ transpositions.

The component supports are disjoint, so the displayed lists may be concatenated. Their total length is
$$
\sum_{\text{cycles }C}(|P\cap C|-1)+\sum_{\text{balanced paths }L}|P\cap L|+\sum_{\text{paired heavy paths }(L_+,L_-)}(|P\cap L_+|+|Q\cap L_-|)=k-c(P,Q)+q(P,Q),
\tag{L13}
$$
where a blue-heavy path with $b$ blue edges contains $b-1$ red edges. Traversing the degree-at-most-two components and writing the lists visits every vertex and edge a constant number of times.
:::

::: {.theorem #thm:couples-seating-swaps-complexity title="Complexity"}
Let $n$ distinct people occupy $n$ labeled seats on a cycle, let $k$ pairwise-disjoint couples be designated, and let one move swap the occupants of any two seats. Given a binary-encoded nonnegative budget $B$, deciding whether all couples can be made adjacent with at most $B$ swaps is NP-complete. It is W[1]-hard parameterized by
$$
s:=n-2k,
$$
the number of people who belong to no couple. More precisely, there is a polynomial parameterized reduction from $r$-MULTICOLORED CLIQUE whose output satisfies $s=2r$ on every branch.
:::

::: {.proof}
Identify each person with the seat occupied initially. The couples form a size-$k$ matching $P$ on the seat vertices. A feasible final seating determines a size-$k$ matching $Q$ of cycle edges. A vertex uncovered by a matching is called a monomer of that matching. Swapping the occupants of seats $x,y$ applies the vertex transposition $(x\,y)$ to every endpoint of the current matching, and every such transposition is the corresponding physical swap. By @lem:fixed-target-couple-distance, a budget $B$ is feasible exactly when some size-$k$ cycle matching $Q$ satisfies
$$
c(P,Q)-q(P,Q)\ge k-B.
\tag{1}
$$

**Source problem.** In $r$-MULTICOLORED CLIQUE, the input graph $G_{\mathrm{src}}$ is partitioned into $r$ labeled color classes, and the question is whether one can choose one vertex from each class so that all chosen vertices are pairwise adjacent. Downey and Fellows proved W[1]-completeness of parameterized INDEPENDENT SET in [“Fixed-parameter tractability and completeness II: On completeness for W[1]”](https://doi.org/10.1016/0304-3975%2894%2900097-3). Graph complementation gives CLIQUE, and the standard colored-copy construction gives $r$-MULTICOLORED CLIQUE parameterized by $r$. We restrict to $2\le r\le |V(G_{\mathrm{src}})|$, since the excluded cases are decided directly without affecting hardness.

For each $r\ge2$, let $T_r^{\mathrm{YES}}$ and $T_r^{\mathrm{NO}}$ be budget-zero one-couple instances on $C_{2r+2}$. The couple occupies seats $0,1$ in the first instance and nonadjacent seats $0,2$ in the second. Both have $s=2r$. Every source branch decided during preprocessing is mapped to the corresponding fixed instance.

Pad the nonempty color classes with isolated vertices so that each is indexed by $[N]=\{1,\ldots,N\}$, and add an isolated dummy value $0$ to every class. For colors $i<j$, define
$$
f_{ij}(x,y)=
\begin{cases}
1,&\text{if values $x$ and $y$ are adjacent in the source graph},\\
0,&\text{otherwise}.
\end{cases}
\tag{2}
$$
The dummy row and column are zero. If a color class is empty or a color pair has no edge, output $T_r^{\mathrm{NO}}$. The main construction may therefore assume that every $f_{ij}$ takes both values $0$ and $1$.

**Eight-seat blocks.** Every block consists of eight consecutive cycle seats numbered $0,\ldots,7$. Its two monomer-free target phases are
$$
E=\{01,23,45,67\},\qquad O_{\mathrm{int}}=\{12,34,56\},
\tag{3}
$$
where phase $O$ also uses the cycle edges entering and leaving the block.

A probe has ports $1,2,5,6$ and internal $P$-edges $04,37$. Phase $E$ induces the port pairing
$$
\Pi_E=(1,5)(2,6),
\tag{4}
$$
while phase $O$ induces
$$
\Pi_O=(1,2)(5,6)
\tag{5}
$$
and leaves a transparent backbone strand through $0,4,3,7$. Joining corresponding ports of two probes by $P$-edges produces one alternating circuit in every phase pair and one additional circuit exactly when the phases agree. Joining port $p$ of the first probe to port $\pi(p)$ of the second for $\pi=(2\ 5)$ produces the additional circuit exactly when the phases differ. Probe pairs therefore implement Boolean equality and inequality tests, each with one baseline circuit.

An $E$-lock has
$$
P_E=\{01,23,45,67\}.
\tag{6}
$$
It contributes four local alternating cycles in phase $E$ and none in phase $O$. An $O$-lock has
$$
P_O=\{07,12,34,56\}.
\tag{7}
$$
It contributes three local cycles in phase $O$ and one in phase $E$. A terminal cut has
$$
P_Z=\{15,26,37\},
\tag{8}
$$
leaves vertices $0,4$ unmatched by $P$, and contributes one private cycle in phase $O$. Only cut vertices are unmatched by $P$.

**Compatibility compiler.** Represent Boolean $1$ by phase $E$ and Boolean $0$ by phase $O$. For a value $x\in\{0,\ldots,N\}$, define threshold literals
$$
X_a(x)=\mathbf 1[x\ge a]\qquad(1\le a\le N).
\tag{9}
$$
For a Boolean function $f:\{0,\ldots,N\}^2\to\{0,1\}$, put
$$
\begin{aligned}
\delta^x_a&=f(a,0)-f(a-1,0),\\
\delta^y_b&=f(0,b)-f(0,b-1),\\
\delta_{ab}&=f(a,b)-f(a-1,b)-f(a,b-1)+f(a-1,b-1).
\end{aligned}
\tag{10}
$$
Twice the two-dimensional telescoping identity, together with
$$
\operatorname{Eq}(X,Y)=1-X-Y+2XY,\qquad \operatorname{Neq}(X,Y)=X+Y-2XY,
\tag{11}
$$
expresses $2f(x,y)$, up to an additive constant, as a multiset of equality and inequality tests between threshold literals and tests of one literal against a constant. The residual coefficient of $X_a$ is
$$
2\delta^x_a+\sum_b\delta_{ab}=\delta^x_a+f(a,N)-f(a-1,N)\in\{-2,-1,0,1,2\},
\tag{12}
$$
and the same bound holds on the other side. A coefficient $\lambda X$ is implemented, up to a constant, by $|\lambda|$ equality tests against $1$ if $\lambda\ge0$ and against $0$ if $\lambda<0$. Hence at most $2N^2+4N$ tests produce
$$
K_f+2f(x,y)
\tag{13}
$$
satisfied tests for a computable integer $K_f$.

Apply this compiler to every $f_{ij}$ and replicate every test
$$
D:=8r
\tag{14}
$$
times. Let $M$ be the total number of replicated relation tests. Every threshold occurrence receives a fresh functional probe, and every constant occurrence receives a fresh reference probe. Write $K_{ij}:=K_{f_{ij}}$. For colors $i<j$, the relation bonus becomes
$$
D K_{ij}+2D f_{ij}(x_i,x_j).
\tag{15}
$$
Let
$$
R^\star:=D\sum_{i<j}(K_{ij}+2).
\tag{16}
$$
The zero dummy entry and an edge entry attain $K_{ij}$ and $K_{ij}+2$, respectively, so
$$
0\le R^\star\le M.
\tag{17}
$$
Every tuple that is not a multicolored clique loses at least $2D=16r$ relation cycles from $R^\star$.

**Protected rails.** Set
$$
\delta:=15r,\qquad W:=H:=M+\delta+1.
\tag{18}
$$
For every color $i$, create one $E$-reference batch and one $O$-reference batch. Assign each constant-reference probe in a unary test to the batches of the color containing its functional literal, using the $E$-batch for constant $1$ and the $O$-batch for constant $0$. Make $N$ value slots for the color. Slot $a$ contains $W$ fresh left-guard probes, all functional probes representing occurrences of $X_{i,a}$, and $W$ fresh right-guard probes. Pair the $j$th left guard with the $j$th right guard by an equality comparator. There are
$$
G:=WrN
\tag{19}
$$
guard pairs.

Rail $i$ consists, in cyclic order, of $H$ $E$-locks, all $E$-reference probes assigned to the rail, another $H$ $E$-locks, the $N$ value slots, $H$ $O$-locks, all $O$-reference probes assigned to the rail, another $H$ $O$-locks, and one cut. Concatenate the $r$ rails around the seat cycle. Let
$$
J:=M+G
\tag{20}
$$
be the number of comparator pairs. There are $h=2J$ probe blocks and $\ell=4Hr$ lock blocks. Every probe and lock is perfectly matched by $P$, while each cut leaves two vertices unmatched. Therefore
$$
n_{\mathrm{out}}=8(h+\ell+r),\qquad k_{\mathrm{out}}=4h+4\ell+3r,
\tag{21}
$$
and
$$
n_{\mathrm{out}}-2k_{\mathrm{out}}=2r.
\tag{22}
$$
The maximum intended lock contribution is
$$
L_{\max}:=14Hr.
\tag{23}
$$

**Clique target.** Choose one value $x_i$ on every rail. Use phase $E$ through slots $1,\ldots,x_i$, phase $O$ afterward and through the cut, and place the second phase change between that cut and the first $E$-lock of the next rail. The target monomers on rail $i$ are vertex $0$ of its first $O$-block and vertex $7$ of its cut, and the canonical phase edges cover every other vertex. The $O$-backbone runs from the first monomer to cut terminal $0$, while the other residual path runs from cut terminal $4$ to the monomer at vertex $7$. Each path has one red-only endpoint and one blue-only endpoint and therefore has equally many $P$- and $Q$-edges. This gives a size-$k_{\mathrm{out}}$ cycle matching with $q(P,Q)=0$.

If the values form a multicolored clique, all guard tests are satisfied, the relation bonus is $R^\star$, the locks contribute $L_{\max}$, and the cuts contribute $r$ cycles. Including one baseline circuit for each comparator, the score is
$$
\Theta:=J+G+R^\star+L_{\max}+r.
\tag{24}
$$
Set
$$
B:=k_{\mathrm{out}}-\Theta.
\tag{25}
$$
This budget is nonnegative. Indeed, $R^\star\le M$ and $J=M+G$ imply
$$
\Theta\le2J+14Hr+r,
\tag{26}
$$
whereas
$$
k_{\mathrm{out}}=8J+16Hr+3r.
\tag{27}
$$
Thus $B\ge6J+2Hr+2r>0$ on the main branch.

**Arbitrary targets.** Let $Q$ be any size-$k_{\mathrm{out}}$ matching of cycle edges. For block $t$, let $b_{t-1},b_t\in\{0,1\}$ indicate whether its incoming and outgoing boundary edges belong to $Q$, let $e_t$ be the number of selected internal cycle edges, and let $m_t$ be the number of target monomers in the block. Counting its eight vertices gives
$$
8=2e_t+b_{t-1}+b_t+m_t.
\tag{28}
$$
Define the cyclic phase word $w=(w_t)$ by $w_t=E$ when $b_t=0$ and $w_t=O$ when $b_t=1$. Equation (28) gives
$$
w_{t-1}\ne w_t\quad\Longleftrightarrow\quad m_t\text{ is odd}.
\tag{29}
$$
Since $Q$ has exactly $n_{\mathrm{out}}-2k_{\mathrm{out}}=2r$ monomers, $w$ has at most $2r$ changes. If $m_t=0$, the incoming boundary bit forces the unique canonical block matching in phase $E$ or $O$.

Delete every noncut block containing a target monomer and delete all $r$ cuts. A probe has at most six incident $P$-edges, a lock has four, and a cut has three. Every alternating cycle destroyed by deletion contains one such edge, and distinct alternating components are edge-disjoint. Hence at most
$$
6(2r)+3r=15r=\delta
\tag{30}
$$
cycles are destroyed. Every surviving block is canonical, and deleting the cuts prevents transparent backbone strands from wrapping into a cycle. Let $\operatorname{Bonus}(w)$ be the number of satisfied relation and guard tests under the outgoing-bit labels of all blocks, including deleted probes, and let $\operatorname{Lock}(w)$ be the corresponding full lock contribution, including deleted locks. Filling in these nonnegative contributions can only increase an upper bound, and $q(P,Q)\ge0$. Therefore every target satisfies
$$
c(P,Q)-q(P,Q)\le J+\operatorname{Bonus}(w)+\operatorname{Lock}(w)+\delta.
\tag{31}
$$

If $\operatorname{Lock}(w)\le L_{\max}-2H$, then even the maximum $G+M$ comparator bonus gives a strict upper bound below $\Theta$, because $H=M+\delta+1$. Otherwise every one of the four lock halves on each rail contains a block in its intended phase. Choose one such block in each half and call it a marker. The choice arc between the second $E$ marker and the first $O$ marker of each rail and the separator arc between its second $O$ marker and the next rail's first $E$ marker have opposite endpoint phases. These $2r$ arcs have disjoint interiors and each contains a phase change. Since the entire word has at most $2r$ changes, every arc contains exactly one change and there are no changes on the complementary reference arcs.

If a choice change lies after the selected marker in the second $E$-lock half, move it to the end of that half. If it lies before the selected marker in the first $O$-lock half, move it to the beginning of that half. These moves change no probe phase and cannot decrease the lock contribution. Move each separator change analogously across the end of its second $O$-lock half, its cut, and the beginning of the next rail's first $E$-lock half to the corridor immediately after the cut. If a choice change lies in a left or right guard bank, move it to the adjacent corridor, preserving every functional phase and weakly increasing the number of satisfied guards. These moves replace $w$ by a phase word whose right-hand side in (31) is no smaller. If a choice change lies between the left and right guard banks of one slot, all $W$ paired guards of that slot disagree. Losing $W=M+\delta+1$ guard bonuses cannot be offset by all $M$ relation bonuses and the $\delta$ anomalous cycles. For the upper-bound analysis, every target of score at least $\Theta$ is therefore dominated by a normalized word with one choice change in an approved corridor, meaning before slot $1$, between consecutive slots, or after slot $N$, on each rail and one separator change after each cut.

Each approved choice corridor in the normalized word determines a unique value $x_i\in\{0,\ldots,N\}$, and all copies of every threshold literal agree. If the decoded tuple is not a multicolored clique, its relation bonus is at most $R^\star-2D$. Equation (31) then gives
$$
\begin{aligned}
c(P,Q)-q(P,Q)
&\le J+G+R^\star-2D+L_{\max}+\delta\\
&=\Theta-r-2D+\delta\\
&<\Theta,
\end{aligned}
\tag{32}
$$
because $2D=16r>\delta-r=14r$. Every target with score at least $\Theta$ therefore decodes a multicolored clique.

If the source has a multicolored clique, its clique target has score $\Theta$, and @lem:fixed-target-couple-distance supplies an ordered sequence of $B$ physical swaps. Conversely, any sequence of at most $B$ swaps reaches a cycle matching of score at least $k_{\mathrm{out}}-B=\Theta$ by (1), and the preceding argument recovers a multicolored clique. This proves the many-one equivalence.

The compiler uses $O(r^2N^2)$ tests before replication, so $M=O(r^3N^2)$. All block counts, thresholds, and the explicitly written output are polynomial in the normalized source size. Equations (22) and the fixed preprocessing instances give $s_{\mathrm{out}}=2r$ on every branch, proving W[1]-hardness.

The decision problem belongs to NP: a size-$k$ cycle matching $Q$ is a polynomial certificate, and @lem:fixed-target-couple-distance lets us compute whether $d(P,Q)\le B$ in linear time. Since the same polynomial reduction starts from the NP-complete unparameterized MULTICOLORED CLIQUE problem, the decision problem is NP-complete.
:::

Consequently, unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm always returns a shortest swap sequence. Unless $\mathrm{FPT}=\mathrm{W[1]}$, no algorithm with running time $f(s)n^{O(1)}$ does so when parameterized only by the number $s$ of unpaired people.

## Computational record

Final usage: 3,899,610 tokens over approximately 6 hours 1 minute.