Higher Hardness Results for the Reconfiguration of Odd Matchings

Reconfiguration describes the process of changing one structure into another. It is often performed by small, reversible steps, so called flips. Reconfiguration has many applications in the areas of optimization [15] or enumeration [6, 18]. We refer to the following surveys for the discussion of additional applications of reconfiguration [19, 23]. Very recently, reconfiguration has also provided substantial insight into the complexity of computing the diameter of polytopes [20, 21], spiking in the result that computing the combinatorial diameter of a polytope is ${\mathrm{\Pi }}_2^p$-hard [25]. Remarkably, all the recent results on the diameter of polytopes study the reconfiguration of perfect matchings.

We study the related problem of the reconfiguration of odd matchings of graphs. An odd matching of a graph $G$ is a matching consisting of edges of $G$ such that all vertices of $G$ are matched except for a single isolated vertex. A flip between two odd matchings is an operation that matches the isolated vertex $v$ of the first matching to another vertex $w$. Subsequently, the vertex that previously shared an edge with $w$ becomes the new isolated vertex. The flip graph of odd matchings of a graph $G$ is a graph that has as vertex set all odd matchings of $G$ and has edges between matchings whenever they can be transformed into one another via a single flip. A flip sequence between an initial matching $M_{in}$ and a target matching $M_{tar}$ is a sequence of matchings $M_{in}=M_0$, $M_1$, $\mathrm{\dots }$, $M_{k-1}$,$M_k=M_{tar}$ such that consecutive matchings only differ by a single flip. In terms of the flip graph, a flip sequence is a path between two matchings. The index $k$ denotes the length of a flip sequence. The flip distance between two odd matchings $M_{in}$ and $M_{tar}$, denoted by $d(M_{in},M_{tar})$, is the minimum over all $k$ such that there exists a flip sequence of length $k$ between $M_{in}$ and $M_{tar}$. This can be interpreted as the length of a shortest path in the flip graph. The diameter of the flip graph is defined as ${\max }_{M_1,M_2}d(M_1,M_2)$ and describes the maximal flip distance between any pair of odd matchings in the flip graph. Similarly, the radius is defined as ${\min }_{M_1}{\max }_{M_2}d(M_1,M_2)$ and describes the minimum maximal distance of a matching $M_2$ to a center $M_1$. Clearly, the diameter of a flip graph is bounded from below by its radius and bounded from above by twice the radius. For an illustration of many of the concepts, we refer to Figure 1.

We reduce directly from $\forall \exists$-SAT to computing the diameter of the flip graph. We will introduce gadgets for clauses and for each type of variable.

As a high level idea, the goal of a flip sequence will be to switch the cycles in all clause gadgets by switching the cycles in all the variable gadgets in a way that places isolated vertices next to clause gadgets. The alternating cycle of an $\exists$-gadget can then be switched in two ways depending on which of the two edges from a central vertex $v$ to the gadget is used to enter the gadget. Each direction for the switch will correspond to an assignment of the variable based on what clauses the isolated vertex is placed next to. In a $\forall$-gadget, there is only one way to enter the gadget from $v$, so the way to switch the cycle is fixed. If the cycle is not crossing in the drawing, the isolated vertex will be placed next to gadgets of clauses that contain the positive literal, and, if the cycle is crossing, next to clauses containing the negative literal.

We now introduce all gadgets of our reduction in more detail. The reduction will be built around one, aforementioned, central vertex $v$.

Clause gadget (Figure 3(a)):

The clause gadget is a 4-cycle that has one vertex which is incident to the later introduced variable gadgets. The idea is to force a perfect matching of the cycle in the initial matching and the other perfect matching in the target matching such that all alternating cycles in variable gadgets need to be switched at some point.

$\forall$-gadget (Figure 3(b)):

For a given variable $x$, the variable gadget consists of a cycle of length twelve, with vertices labeled $1$ to $12$ along the cycle, as well as two additional diagonals from vertex $2$ to vertex $10$ and vertex $3$ to vertex $11$ in the cycle that form the crossing as seen in Figure 3(b). The vertex with label $1$ has an edge that is connected to a central vertex $v$. Two vertices, labeled $3$ and $9$, have edges to all clause gadgets that correspond to clauses that contain $\overline{x}$. Two vertex, labeled $4$ and $10$, are incident to edges to all clause gadgets that correspond to clauses that contain $x$. If $M_{in}\cup M_{tar}$ contains an alternating cycle on a $\forall$-gadget, then this cycle can either contain the introduced crossing or not. To see a crossed and uncrossed cycle, see Figure 4. The two options will encode the truth value of the corresponding variable.

$\exists$-gadget (Figure 3(c)):

The $\exists$-gadget corresponding to a variable $y$ consists of a cycle with twelve edges and vertices labeled $1$ to $12$ along the cycle. Two adjacent vertices, labeled $1$ and $12$ are incident to an edge to the vertex $v$. Two vertices, labeled $2$ and $10$ are incident to edges to all gadgets of clauses that contain $y$. Similarly, two vertices, labeled $3$ and $11$ are connected to gadgets of clauses that contain $\overline{y}$. If the union $M_{in}\cup M_{tar}$ contains an alternating cycle on an $\exists$-gadget, the cycle can be switched in two ways depending on which of the two edges incident to $v$ is used to switch the cycle. These two choices will encode the two truth values of the corresponding variable.

Forcing the position of the isolated vertex:

If we take $s$ to be the number of vertices in all clause gadgets, $\forall$-gadgets and $\exists$-gadgets combined, we obtain by [1, Theorem 10] that any connected component of the flip graph of odd matchings of the constructed graph has diameter at most $c\cdot (s+1)$ for a constant $c$. We attach to $v$ a path $P$ of length $\mathrm{\ell }=2c\cdot (s+1)$ (See Figure 5). If the isolated vertex of at least one of the matchings is placed at the vertex $w$ of $P$ that is farthest away from $v$, then flipping edges along the path already takes $\frac{\mathrm{\ell }}{2}$ flips, which is at least as much as it takes to reconfigure two odd matchings if both have their isolated vertex placed on some clause gadget, $\forall$-gadget, or $\exists$-gadget.

The reduction:

Now, let $\varphi$ be a Boolean formula on variables $x_1$,…,$x_{m_1}$ and $y_1,\mathrm{\dots },y_{m_2}$. We construct a graph $G$ as follows: Start from a single vertex $v$. For every $x_i$ introduce a $\forall$-gadget and connect it to $v$ as described above. For every $y_i$ introduce an $\exists$-gadget and connect it to $v$ as described. Further, introduce a clause gadget for every clause $C$ in $\varphi$ and connect each clause gadget to all the variable gadgets that correspond to variables in the clause. The connection happens in one of two ways described above depending on whether $x\in C$ or $\overline{x}\in C$ (resp. $y$ or $z$). Then add the path of length $\mathrm{\ell }$ at $v$ to obtain a final graph $G^{\prime }$.

First, we need to make sure that the diameter is well defined in this setting.

We show Proposition 4 by showing that $G^{\prime }$ fulfills the characterization of graphs for which the flip graph is connected from [1, Theorem 3].

From now on, we will call a pair of matchings $M_{in}$ and $M_{tar}$ such that $d(M_{in},M_{tar})$ equals the diameter of the flip graph a maximizing pair. We will make structural observations on how a maximizing pair looks like. Also, let $v_{M_{in}}$ and $v_{M_{tar}}$ denote the isolated vertices of $M_{in}$ and $M_{tar}$.

We reduce from $\exists \forall \exists$-SAT to computing the radius of the flip graph. We now introduce all gadgets for our reduction that will again be built around one central vertex $v$.

Clause gadget (Figure 3(a)):

The clause gadget is the same as in Section 3.

First $\exists$-gadget (Figure 3(b)):

The first $\exists$-gadget is the same as the $\forall$-gadget of Section 3.

$\forall$-gadget (Figure 6):

The $\forall$-gadget corresponding to a variable $y$ consists of a cycle with $14$ edges and vertices labeled $1$ to $14$ along the cycle, as well as four diagonals, from $2$ to $12$, $3$ to $11$, $4$ to $12$, and $3$ to $13$, of the cycle that form the two crossings in Figure 6. Two vertices, $4$ and $10$, have edges to clauses that contain the positive literal $y$ and two vertices, $5$ and $11$, with edges to clauses containing the negative literal $\overline{y}$ and vertex $1$ has an edge from the vertex $v$.

Second $\exists$-gadget (Figure 3(c)):

The second exists gadget coincides with the $\exists$-gadget of Section 3. Notation wise, the variables corresponding to those gadgets will now be called $z$ instead of $y$.

Forcing position of the isolated vertices:

We conclude the construction by attaching two paths to $v$. Let $s$ be the number of vertices in clause and variable gadgets. We set $\mathrm{\ell }=2c\cdot (s+1)$ where $c$ is chosen according to [1, Theorem 10] such that $\mathrm{\ell }$ is larger than twice the diameter of the flip graph of odd matchings on $v$ and the clause and variable gadgets. We add a path $p$ of length $\mathrm{\ell }$ and attach one end to $v$ and to the other end we attach a four-cycle $Z$. Further, let $L=2c\cdot (s+\mathrm{\ell }+1)$ and add a path $P$ of length $L$ and attach one end of $P$ to $v$. No matter what a matching $M_{in}$ in the center of the flip graph looks like, a matching $M_{tar}$ can maximize the distance to $M_{in}$ by having an isolated vertex at $v_{M_{tar}}$, the end vertex of $P$ that is not attached to $v$ and by differing from $M_{in}$ on $Z$. By doing so, any flip sequence is forced to traverse both $p$ and $P$. Vice versa, by having the isolated vertex of $M_{in}$ placed on $Z$ it can be guaranteed that a flip sequence traverses $p$ only once instead of twice.

The reduction:

Now, let $\psi$ be a Boolean formula on variables $x_1$,…,$x_{m_1}$, $y_1,\mathrm{\dots },y_{m_2}$ and $z_1,\mathrm{\dots },z_{m_3}$. We construct a graph $G$ as follows: Start from a single vertex $v$. For every $x_i$ introduce a first $\exists$-gadget and connect it to $v$ as described above. Repeat for all $y_i$ and $\forall$-gadgets and all $z_i$ and the second $\exists$-gadget. Further, for every clause $C$ in $\psi$ introduce a clause gadget and connect the gadget to all the variable gadgets that correspond to variables in the clause. The connection happens in one of two described ways depending whether $x\in C$ or $\overline{x}\in C$ (resp. $y$ or $z$). Then add the paths $p$ and $P$ as described to obtain a final graph $G^{\prime \prime }$. Again, we need to make sure that the radius is well defined in this setting.

Again, we verify this by checking the characterization from [1, Theorem 3].

We will again give a characterization of pairs of matchings, which can determine the radius. We will argue that, without loss of generality, we do not have to consider all other pairs of matchings but only a set of candidates. As a high level argument, we make sure that in a candidate pair we cannot make a change to $M_{tar}$ locally in a single gadget such that the flip distance to $M_{in}$ increases and we cannot immediately make a change to $M_{in}$ in a single gadget such that the flip distance decreases even if $M_{tar}$ is changed locally to respond to the changes to $M_{in}$.

With Lemma 9 in mind, we describe the high level strategies for $M_{in}$, $M_{tar}$ and a shortest flip sequence:

Since all clause gadgets contain alternating cycles, a shortest flip sequence will have to switch them all by entering them through a variable gadget. Adjacency relations of gadgets correspond to containment relations of variables in clauses.

For the first $\exists$-gadget, while switching an uncrossed cycle, the isolated vertex will be next to clause gadgets containing the positive literal, otherwise, if the cycle is crossed, the clauses with negative literals can be switched. Also note, that $M_{in}$ can determine, whether the cycle is crossed or uncrossed. $M_{in}$ may choose not to control the existence of the crossing if the value of a particular variable does not matter.

For the $\forall$-gadget, while switching the cycle, the isolated vertex is next to clauses with positive literals if the cycle is crossing twice or not at all, however if it crosses once, the isolated vertex is placed next to clauses with negative literals. While $M_{in}$ can control to add one crossing to the cycle or not, the existence of a second crossing will then always be controlled by $M_{tar}$.

For the second $\exists$-gadget, there is only one option for an alternating cycle up to swapping $M_{in}$ and $M_{tar}$. The direction of traversal is then chosen by the flip sequence depending on which of the two edges incident to $v$ is chosen to enter the gadget. The direction of traversal then determines whether the isolated vertex will be placed next to clauses with positive or negative literals.

The reduction from Set Cover to finding minimum flip sequences is illustrated in Figure 8. For every set in $S$ from the Set Cover instance we add a path with $\mathrm{\ell }$ vertices to the graph $G^{\prime \prime \prime }$, for some even $\mathrm{\ell }$ that will be fixed later. We construct $M_{in}$ and $M_{tar}$ such that they form a perfect matching of the paths. For every integer from $1$ to $n$ (that denote the elements within the sets), we add a $4$-cycle to $G^{\prime \prime \prime }$ such that $M_{in}$ and $M_{tar}$ cover the cycle alternatingly. At last, we add one single vertex to $G^{\prime \prime \prime }$ such that this vertex is the isolated vertex in both $M_{in}$ and $M_{tar}$. For each path corresponding to a set $s_i$ in $S$, we add an edge from one end of the path to the isolated vertex and edges from the other end to all gadgets that correspond to integers that are contained in $s_i$. The strategy for a flip sequence is to traverse a set gadget in order to be able to flip the integer gadgets for integers that are contained in the set. After that the flip sequence has to traverse the set gadget back to the initial isolated vertex. Since $G^{\prime \prime \prime }$ is bipartite (see green/orange partition in Figure 8), there are no shortcuts that skip the traversal of set gadgets.

We have shown that computing the diameter of the flip graph of combinatorial odd matchings is ${\mathrm{\Pi }}_2^p$-complete and computing the radius of a the flip graph is ${\mathrm{\Sigma }}_3^p$-complete. By doing so, we provide two naturally occuring problems that fall into these complexity classes. Further, by reducing Set Cover to the problem of finding shortest flip sequences between odd matchings we show that the problem is $\mathrm{𝖠𝖯𝖷}$-hard and does not admit any global constant factor approximation.

The following open questions arise from our results:

1. 1.

   Since the reconfiguration of matchings is closely tied to complexity results in polytopes we motivate the question whether it is ${\mathrm{\Sigma }}_3^p$-hard to compute the combinatorial radius/center of a polytope. We remark that the result for the diameter of the flip graph in [25] uses a so called canonical structure, that is, a structure that can be reached from any other structure in a reasonable number of flips. An upper bound on the diameter then follows from flipping from any initial structure to the canonical structure and then to the target structure. Therefore, by computing the radius, a center of the flip graph is implicitly also computed. This means that so far computing the radius is only shown to be ${\mathrm{\Pi }}_2^p$-hard.

2. 2.

   Can similar results on the complexity of computing the diameter and radius also be shown in a geometric setting? While in the combinatorial setting, we can control, which edges are part of the input graph $G$ and which are not, in the geometric setting all edges between any two points in the plane can theoretically occur in $M_{in}$, $M_{tar}$ or any intermediate matching, the only degree of freedom for constructions is the placement of the points.