On the complexity of the odd-red bipartite perfect matching polytope
1 : Department of Mathematics, ETH Zurich
2 : Department of Mathematics [ETH Zurich]
It is a notorious open question in theoretical computer science whether all efficient randomized algorithms can be derandomized.
One of the most prominent problems that admits a polynomial-time randomized algorithm, but for which no polynomial-time deterministic algorithm is known, is the \emph{exact bipartite perfect matching problem}.
In this problem, given a bipartite graph with all edges colored red or blue, and an integer $k$, the question is whether there exists a perfect matching that contains exactly $k$ red edges.
Recent progress towards deterministic algorithms for this problem crucially relies on a good polyhedral understanding of the underlying perfect matching problem.
Motivated by this, Jia, Svensson, and Yuan~[SODA~2023] show that the extension complexity of the exact bipartite perfect matching polytope is exponential in general.
Interestingly, their result is true even if---instead of fixing the exact number---only the parity of the number of red edges is restricted, resulting in the \emph{red-odd bipartite perfect matching problem}.
In their proof, Jia, Svensson, and Yuan introduce a relaxation of the corresponding red-odd perfect matching polytope with exponentially many constraints.
Their work left open whether the given relaxation is an exact description.
In this work, we answer this question negatively and reveal additional hurdles in the quest of obtaining correct polyhedral descriptions.
First, we show that the relaxation admits fractional vertices.
Next, we prove that separating over the relaxation is \NP-hard, even though red-odd bipartite perfect matching can be solved efficiently.
This uncovers challenges for using the suggested constraint family to obtain an exact description.
Finally, we show that any inequality description of the red-odd perfect matching polytope requires arguably complex constraints, which is in stark contrast to most other efficiently solvable combinatorial optimization problems.
Concretely, we reveal a family of facets for which any representation in the form $a^\top x \leq b$ with $a\in\mathbb{Z}^{E}$ and $b\in\mathbb{Z}$ requires large and diverse coefficients in $a$, which is in particular not the case for the constraints considered by Jia, Svensson, and Yuan.
| Type : | : | Soumission de Résumé |
| Thématiques | : | Présentation régulière (~20 min) |
| PDF version | : |  PDF version |
