On Finding $\mathrm{\ell }$-Th Smallest Perfect Matchings

Our main result can be equivalently stated in a different way: Consider the following problem, which we call $\mathrm{\ell }$-th Smallest Perfect Matching (${\text{SPM}}_{\mathrm{\ell }}$): Given a weighted graph $G$, an integer $k$, and a natural number $\mathrm{\ell }$, decide whether $G$ contains an $\mathrm{\ell }$-th smallest perfect matching of weight exactly $k$. Here, the notion of $\mathrm{\ell }$-th smallest perfect matchings is defined recursively: $1$st-smallest perfect matchings are exactly the minimum-weight perfect matchings, and for $\mathrm{\ell }\ge 2$, $\mathrm{\ell }$-th smallest perfect matchings are the perfect matchings of minimum weight among all perfect matchings that are not ${\mathrm{\ell }}^{\prime }$-th smallest for any . In this language, our result is an algorithm that solves ${\text{SPM}}_{\mathrm{\ell }}$ in time $n^{𝒪(\mathrm{\ell })}$.

Similar next-to-optimal problems have been studied in the literature before. In particular, there is a line of work on finding next-to-shortest paths in directed or undirected graphs. In these problems, we want to find a next-to-shortest $(s,t)$-path in a weighted graph $G$, i.e. the path should have minimum weight among all $(s,t)$-paths that are not shortest paths. This problem is NP-hard on directed graphs [22], but admits polynomial-time algorithms on undirected graphs [18, 21, 23, 31, 33]. Note that the NP-hardness result in [22] heavily relies on allowing edges to have weight zero. Indeed, the so-called detour problem – decide whether all $(s,t)$-shortest paths in a given unweighted directed graph have the same length or not – is very similar but does not allow for zero-weight edges, and its complexity status is still unresolved [15].

Instead of asking for a perfect matching of $\mathrm{\ell }$-th smallest weight, one could instead ask for $\mathrm{\ell }$ distinct perfect matchings while minimizing their combined weight. This is a conceptually different problem which is equivalent to repeatedly ($\mathrm{\ell }$ times) finding the best solution distinct from previously obtained solutions. Such $k$-best enumeration problems have been studied for a number of combinatorial optimization problems: Murty [26] first showed a polynomial-time algorithm for the $k$-best bipartite perfect matching problem. Later, the time complexity was improved by Chegireddy and Hamacher [2]. For more information, we refer the reader to the survey by Eppstein [11].

Our second contribution in this paper is to strengthen the connection between EWPM and related cycle problems, as we will outline here.

Consider the following problem, which we call Exact Cycle Sum (ECS): Given an undirected graph $G$ with conservative (i.e. no negative cycles) edge-weights and an integer $k$, decide whether $G$ contains a set of disjoint cycles of weight exactly $k$. A directed version of ECS with general weights has been studied e.g. by Papadimitriou and Yannakakis [27]. Concretely, they proved that the directed version of ECS is equivalent to EWPM on bipartite graphs. We extend this result by proving that the undirected problem ECS as defined above is equivalent to EWPM on general graphs. Our reductions preserve the encoding of the weights. Hence, we obtain as a result that ECS is in RP if weights are encoded in unary, and NP-complete if weights are encoded in binary.

Another interesting problem on cycles in graphs is the so-called Shortest Odd Cycle problem (SOC): Given an undirected graph $G$ with conservative edge-weights and an integer $k$, decide whether $G$ contains a cycle of odd weight at most $k$. SOC was recently studied by Schlotter and Sebő [28] (they use slightly different but equivalent definition, see Section 2.3 for more details), who proved that it is equivalent to finding minimum-weight odd $T$-joins. They also point out that SOC is contained in RP for unary weights, due to a result by Geelen and Kapadia [13], and therefore conjecture that the problem should be contained in P as well. Interestingly, the algorithm in [13] follows from a reduction to a problem on perfect matchings that can then be solved using the techniques of Mulmuley, Vazirani, and Vazirani [24]. In fact, this problem on perfect matchings has independently been studied by El Maalouly, Steiner, and Wulf [8] who called it Bounded Correct-Parity Perfect Matching (BCPM): Given a weighted graph $G$ and an integer $k$, decide whether $G$ contains a perfect matching $M$ of weight $w(M)$ at most $k$ and with $w(M){\equiv }_{2}k$ (where ${\equiv }_2$ is used to denote mod $2$ equivalence). El Maalouly, Steiner, and Wulf use BCPM on bipartite graphs as a subroutine for a parameterized algorithm for EM on bipartite graphs. To this end, they prove that BCPM on bipartite graphs is in P, by reducing it to the directed version of SOC (which can be solved via dynamic programming). In this paper, we extend this set of results by proving that BCPM on general graphs is equivalent to SOC as defined above. Unfortunately, we are not able to give deterministic polynomial-time algorithms for either problem, but any such deterministic polynomial-time algorithm for SOC or BCPM would immediately imply that the parameterized algorithm from [8] also works on general graphs. Furthermore, our results highlight that the two equivalent problems SOC and BCPM can be seen as a stepping stone for solving unary EWPM, and that it might be reasonable to tackle them first.

Concretely, some interesting further questions that remain unresolved are: Can we solve SOC and BCPM in deterministic polynomial time? The conjecture RP $=$ P suggests that for unary weights, one should be able to do it. Interestingly, we know very little about the case of weights encoded in binary: If the weights are encoded in binary, it is not known whether SOC or BCPM are in RP or NP-hard (since the randomized algorithm in [13] works only for unary weights). Note that the same questions were also asked by Schlotter and Sebő [28].

While in the general case, derandomization of unary SOC and BCPM remains open, combining our algorithm for EWPM with our reductions also implies that BCPM, SOC, and ECS can be deterministically solved in time $n^{O(\mathrm{\ell })}$ if at most $\mathrm{\ell }$ many different possible weights of perfect matchings (cycle sums, respectively) appear in the instance.

As mentioned before, EWPM with weights restricted to $0$ and $1$ is called the Exact Matching Problem (EM). Derandomizing the known randomized algorithm is an important open problem. Solution approaches have mainly been focused on three directions: Finding deterministic approximation algorithms, finding deterministic algorithms on restricted graph classes, and identifying other polynomial-time equivalent problems.

• $\mathrm{■}$

  In terms of approximation algorithms for EM, Yuster [32] proved that one can find an almost exact matching (a matching of weight exactly $k$ that may fail to cover two vertices of the graph) in deterministic polynomial time if an exact matching exists in the graph. One could interpret this as an approximation result that relaxes the perfect matching constraint. If we relax the exactness constraint instead, recent progress includes a two-sided $2$-approximation algorithm on bipartite graphs by El Maalouly [5], and a one-sided $3$-approximation algorithm on bipartite graphs by Dürr, El Maalouly, and Wulf [3].

• $\mathrm{■}$

  EM has been studied on various restricted graph classes. In fact, Karzanov [19] proved already in 1987 that EM can be solved in deterministic polynomial time on complete and complete bipartite graphs. This has been generalized in different ways: El Maalouly and Steiner [7] gave deterministic polynomial-time algorithms on graphs with bounded independence number (and bipartite graphs of bounded bipartite independence number). In the case of bipartite graphs, this was improved to an FPT-algorithm by El Maalouly, Steiner, and Wulf [8]. In the general case, Murakami and Yamaguchi [25] gave an FPT-algorithm that is paramatrized by the independence number and the minimum size of an odd cycle transversal.

  El Maalouly, Haslebacher, and Wulf [6] used Karzanov’s original techniques to prove that EM restricted to chain graphs, unit-interval graphs, and complete $r$-partite graphs is in P. They also showed that a local search algorithm works in deterministic polynomial time on complete $r$-partite graphs, graphs of bounded neighborhood diversity, and graphs without complete bipartite $t$-holes.

  Finally, it is also possible to derandomize the randomized algorithm on some graph classes, e.g. by finding so-called Pfaffian orientations. Concretely, Vazirani [30] showed how to do this for $K_{3,3}$-free graphs, and Galluccio and Loebl [12] obtained Pfaffian orientations for graphs of bounded genus.

• $\mathrm{■}$

  Previously, some effort has also been made to identify other natural problems that are polynomial-time equivalent to EM. We already mentioned some of these results in Section 1.2. Besides the mentioned cycle problems, EM is also known to be equivalent to a problem called Top-k Perfect Matching [9].

• $\mathrm{■}$

  Finally, Jia, Svensson, and Yuan [16] recently proved that the bipartite exact matching polytope has exponential extension complexity. This stands in contrast to the bipartite perfect matching polytope, which is known to be integral.

We remark that many of these algorithmic results only hold for 0-1-weighted EWPM, and do not even translate to unary EWPM since they often involve very specific graph structures or parameters. In contrast, our parameterized algorithm works even for binary encoding of weights in EWPM.

We formally define EWPM and related problems in Section 2, where we also recall some of the most important concepts from the literature. In Section 3, we introduce the $\mathrm{\ell }$-th Smallest Perfect Matching (${\text{SPM}}_{\mathrm{\ell }}$) problem, and we prove that it can be solved deterministically in time $n^{𝒪(\mathrm{\ell })}$. In Section 4, we explain our reductions between cycle and matching problems. Full proofs of all statements in Section 4 can be found in the Appendix of the full version.

An important and common tool for working with perfect matchings is the symmetric difference. The symmetric difference of two sets $X,Y$ is defined as $X\mathrm{\Delta }Y≔(X\cup Y)\setminus (X\cap Y)$. It is a well-known fact that the symmetric difference $M\mathrm{\Delta }{M}^{\prime }$ of two perfect matchings $M,M^{\prime }$ in a graph $G=(V,E)$ always consists of a set of vertex-disjoint even cycles. In other words, there exist vertex-disjoint even cycles $C_1,\mathrm{\dots },C_p\subseteq E$ such that $M\mathrm{\Delta }{M}^{\prime }={⨆}_{i=1}^p{C}_i$. We say that $C_i$ is a cycle from $M\mathrm{\Delta }{M}^{\prime }$, and we sometimes use the letter $p$ to refer to the number of cycles in $M\mathrm{\Delta }{M}^{\prime }$. Further, we recall that every cycle $C$ in $M\mathrm{\Delta }{M}^{\prime }$ is alternating in both $M$ and $M^{\prime }$ (an even cycle $C$ of $G$ is called $M$-alternating if and only if it alternates between edges in $M$ and edges not in $M$). The set $M\mathrm{\Delta }C$ is again a matching of the same cardinality as $M$. We often refer to this property by saying that we switch $M$ along $C$ to obtain the new matching $M\mathrm{\Delta }C$. Naturally, the matchings $M\mathrm{\Delta }C$ and $M$ differ exactly in $C$, i.e. $(M\mathrm{\Delta }C)\mathrm{\Delta }M=C$.

Recall again that $M\mathrm{\Delta }{M}^{\prime }$ is a collection of vertex-disjoint even cycles $C_1,\mathrm{\dots },C_p\subseteq E$, and that each of the cycles $C_1,\mathrm{\dots },C_p$ is both $M$-alternating and $M^{\prime }$-alternating. Hence, given both $M,M^{\prime }$, some new perfect matchings of $G$ can be obtained by switching either $M$ or $M^{\prime }$ along a subset of the cycles $C_1,\mathrm{\dots },C_p$. In particular, we can perform the switching operations independently of each other because the cycles are vertex-disjoint.

Finding a minimum-weight perfect matching is a classical problem that has been studied extensively. We will define it as follows.

It is well-known that MWPM is in P (even if weights are encoded in binary, see e.g. [20]). Moreover, finding a maximum-weight perfect matching is analogous to finding a minimum-weight perfect matching, and hence that can also be done in deterministic polynomial time. Since both of these problems are in P, it then seems natural to ask whether we can also test for a perfect matching of weight exactly $k$ in polynomial time.

As mentioned in Section 1, the variant of EWPM with weights from $\{0,1\}$ is also known as Exact Matching (EM), and it is contained in RP [24]. Moreover, this also implies that EWPM with weights encoded in unary is contained in RP. In contrast, EWPM with weights encoded in binary is NP-complete [27, 14]. Note that this constitutes a major difference to MWPM, where both the unary and binary variant admit efficient algorithms.

The following problem BCPM is at most as hard as EWPM, and it was used in [8] as part of an algorithm for EM.

The randomized algorithm for unary EWPM also implies a randomized algorithm for unary BCPM. Interestingly, the complexity of binary BCPM remains open. In particular, it is not known whether binary BCPM is NP-hard or not.

Many problems on finding shortest paths and cycles in graphs with non-negative edge-weights can be solved efficiently. On the other hand, allowing for negative weights usually makes those problems NP-hard as they now include problems such as finding Hamiltonian paths or cycles. An interesting compromise is provided by conservative edge-weights.

Using established techniques (see e.g. Johnson’s algorithm [17] or Suurballe’s algorithm [29]), conservative weights on directed graphs can be turned into non-negative weights while maintaining the total weight of each cycle. Hence, cycle problems in directed graphs with conservative edge-weights are usually not harder than their non-negative variants. However, in the case of undirected graphs, the same technique is not applicable, and it turns out that there are interesting cycle problems on undirected graphs with conservative edge-weights that relate to EWPM and BCPM. Concretely, we will work with the two problems Exact Cycle Sum (ECS) and Shortest Odd Cycle (SOC), defined on graphs with conservative weights.

Note that the definition of SOC by Schlotter and Sebő [28] as well as Geelen and Kapadia [13] slightly differs from ours: They require the cycle to have odd length (i.e. an odd number of edges) instead of odd weight. However, it is not hard to see that the two versions are polynomial-time equivalent. Indeed, by splitting even-weight edges, we can ensure to get a graph with only odd-weight edges, yielding a reduction from our odd-weight version to the odd-length version. To reduce the odd-length version to the odd-weight version, it suffices to manipulate the weights, replacing the weight $w(e)$ of each edge $e$ with $2|V|w(e)+1$.

As mentioned in Section 1.2, El Maalouly et al. [8] gave a polynomial-time algorithm for BCPM on bipartite graphs by reducing it to a directed version of SOC. An analogous connection between EWPM on bipartite graphs and the directed version of ECS has been observed by Papadimitriou and Yannakakis [27] already in 1982. In Section 4, we will extend these connections between cycle and matching problems by proving equivalence of ECS (undirected) and EWPM (on general graphs), and SOC (undirected) and BCPM (on general graphs), respectively.

The goal of this section is to prove Theorem 9. We start by recalling some useful facts about the perfect matching polytope from Chapter 11 of the standard textbook by Korte and Vygen [20]. For this, it will be convenient to use the notation $\delta (v)$ to denote the set of edges incident to a vertex $v\in V$. Similarly, for all $A\subseteq V$, we use $\delta (A)$ to denote the set of edges with one endpoint in $A$ and the other in $V\setminus A$. Moreover, we denote by $𝒜$ the set of all odd-cardinality sets $A\subseteq V$, i.e. $𝒜≔\{A\subseteq V:|A|{\equiv }_{2}1\}$.

For the remainder of this section, let $G=(V,E)$ be a graph with edge-weights $w:E\to \mathbb{Z}$. The integer linear program

with variables $\{x_e\mid e\in E\}$ captures the problem of finding a minimum-weight perfect matching in $G$. Now consider the following LP relaxation

where additional odd-set constraints were added. By the famous result of Edmonds [4], adding these additional odd-set constraints is necessary and sufficient to make the LP integral. In other words, the basic feasible solutions to the LP are exactly the perfect matchings of $G$. The dual LP is now given by

where we introduced a variable $z_A$ for all $A\in 𝒜$. By strong duality, the optimal value of the primal and the dual coincide.

Unsurprisingly, it turns out that all minimum-weight perfect matchings are contained in the residual graph with respect to a given optimal solution $z$. However, there might exist perfect matchings in the residual graph that are not minimum-weight perfect matchings of $G$. Hence, we need an extra condition to exactly characterize which perfect matchings in the residual graph are minimum-weight in $G$. Eppstein [10] shows such a result for bipartite graphs. We present here the natural generalization to all graphs. This essentially follows from the complementary slackness theorem [20].