Inapproximability of shortest paths on perfect matching polytopes Jean Cardinal10000000223120967and Raphael Steiner20000000242346136
2025-05-05
1
0
571.62KB
15 页
10玖币
侵权投诉
Inapproximability of shortest paths on perfect matching
polytopes?
Jean Cardinal1[0000−0002−2312−0967] and Raphael Steiner2[0000−0002−4234−6136]
1Universit´e libre de Bruxelles (ULB), Brussels, Belgium
jean.cardinal@ulb.be
2ETH Zurich, Z¨urich, Switzerland
raphaelmario.steiner@inf.ethz.ch
Abstract. We consider the computational problem of finding short paths in the skeleton of
the perfect matching polytope of a bipartite graph. We prove that unless P=NP, there is no
polynomial-time algorithm that computes a path of constant length between two vertices at
distance two of the perfect matching polytope of a bipartite graph. Conditioned on P6=NP,
this disproves a conjecture by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM
Journal on Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential
Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm
computing a path of length at most 1
4−o(1)log N
log log Nbetween two vertices at distance two
of the perfect matching polytope of an N-vertex bipartite graph. These results remain true
if the bipartite graph is restricted to be of maximum degree three.
The above has the following interesting implication for the performance of pivot rules for the
simplex algorithm on simply-structured combinatorial polytopes: If P6=NP, then for every
simplex pivot rule executable in polynomial time and every constant k∈Nthere exists a
linear program on a perfect matching polytope and a starting vertex of the polytope such
that the optimal solution can be reached in two monotone steps from the starting vertex, yet
the pivot rule will require at least ksteps to reach the optimal solution. This result remains
true in the more general setting of pivot rules for so-called circuit-augmentation algorithms.
Keywords: Polytopes ·Perfect matchings ·Linear programming ·Simplex method ·
Pivot rules ·Circuit-augmentation ·Inapproximability ·Combinatorial reconfiguration
1 Introduction
The history of linear programming is intimately intertwined with that of Dantzig’s simplex algo-
rithm. While the simplex and its many variants are among the most studied algorithms ever, a
number of fundamental questions remain open. It is not known, for instance, whether there exists a
pivot rule that makes the simplex method run in strongly polynomial time. Since the publication of
the first examples of linear programs that make the original simplex algorithm run in exponential
time, many alternative pivot rules have been proposed, fostering a tremendous amount of work in
the past 75 years, both from the combinatorial and complexity-theoretic point of views.
The simplex algorithm follows a monotone path on the skeleton of the polytope defining the lin-
ear program. The following natural question was recently raised by De Loera, Kafer, and Sanit`a [14]:
?The second author was supported by an ETH Postodctoral Fellowship.
arXiv:2210.14608v1 [math.OC] 26 Oct 2022
2 J. Cardinal and R. Steiner
“Can one hope to find a pivot rule that makes the simplex method use a shortest monotone path?”.
As an answer, they proved that given an initial solution to a linear program, it is NP-hard to
find a 2-approximate shortest monotone path to an optimal solution. It implies that unless P=NP,
no polynomial-time pivot rule for the simplex can be guaranteed to reach an optimal solution in a
minimum number of steps.
A similar result can also be deduced from two independent contributions, by Aichholzer, Car-
dinal, Huynh, Knauer, M¨utze, Steiner, and Vogtenhuber [2] on one hand, and by Ito, Kakimura,
Kamiyama, Kobayashi, and Okamoto [26] on the other hand. They proved that the above result
holds for perfect matching polytopes of planar and bipartite graphs, albeit with a slightly weaker
inapproximability factor of 3/2 instead of 2. Ito et al. [26] conjecture that there exists a constant-
factor approximation algorithm for the problem of finding a shortest path between two perfect
matchings on the perfect matching polytope.
Our main result is a disproof of this conjecture under the P6=NP assumption: Strength-
ening the previous inapproximability results mentioned above, we show that unless P=NP no
k-approximation for a shortest path between two vertices at distance 2 of a bipartite perfect match-
ing polytope can be found in polynomial time, for any (arbitrarily large) choice of k∈N. We
also give an even stronger inapproximability result under the Exponential Time Hypothesis (ETH).
The latter states that the 3-SAT problem cannot be solved in worst-case subexponential time, and
is one of the main computational assumptions of the fine-grained complexity program [38]. As a
consequence, there is not much hope of finding a pivot rule for the simplex algorithm yielding good
approximations of the shortest path towards an optimal solution, even when the linear program is
integer and its associated matrix totally unimodular.
1.1 Our result
We consider the complexity of computing short paths on the 0/1 polytope associated with perfect
matchings of a bipartite graph. Given a balanced bipartite graph G= (V, E), where Vis partitioned
into two equal-size independent sets Aand B, we define the perfect matching polytope PG⊆REof
Gas the convex hull of the 0/1 incidence vectors of perfect matchings of G.
It is well-known (see e.g. Chapter 18 in [36]) that for bipartite graphs G, there is a nice halfspace
representation of PG. An edge-vector (xe)e∈E∈REis in PGif and only if the following hold.
X
e3v
xe= 1,(∀v∈V) (1)
xe≥0,(∀e∈E).(2)
The above is a compact encoding of PG, with a number of constraints and variables of size
polynomial in G. The assumption that Gis bipartite is crucial here: For non-bipartite Gthe
polytope defined by the above constraints has non-integral vertices and is thus not a representation
of PG[36]. The matrix of this representation of a perfect matching polytope of a bipartite graph
Gis simply the vertex-edge-incidence matrix of G, which is totally unimodular. The problem of
maximizing a linear functional wTxsubject to constraints (1) and (2) corresponds exactly to the
problem of finding a perfect matching Mof Gwhose weight Pe∈Mweis maximal.
Given that the simplex algorithm moves along the edges of a polytope, it is crucial for our
considerations to understand adjacency of vertices on PG. The following result is well-known [12,27].
Inapproximability of shortest paths on perfect matching polytopes 3
Lemma 1. For a bipartite graph G, two vertices of PGcorresponding to two perfect matchings M1
and M2are adjacent in the skeleton of PGif and only if the symmetric difference M1∆M2is a
cycle in G.
This cycle is said to be alternating in both matchings, and one matching can be obtained from
the other by flipping this alternating cycle. In general, we will say that two perfect matchings are
at distance at most kfrom each other on PG, for some positive integer k, if one can be obtained
from the other by successively flipping at most kalternating cycles.
. . .
. . .
Fig. 1. Two perfect matchings at distance two on the perfect matching polytope, but whose symmetric
difference consists of an arbitrarily large number of even cycles.
Note that given any two perfect matchings M1and M2of a bipartite graph G, it is always
the case that M1∆M2is a collection of vertex-disjoint even cycles that are alternating in both
matchings. The number of such cycles is therefore an upper bound on the distance between M1
and M2on PG. Interestingly, this upper bound can be arbitrarily larger than the actual distance.
Figure 1 shows a construction of a graph Gwith two matchings at distance two on PG, whose
symmetric difference consists of an arbitrary number of cycles.
Our main result is the following.
Theorem 1. Let k≥2be any fixed integer. Unless P=NP, there does not exist any polynomial-
time algorithm solving the following problem:
Input: A bipartite graph Gof maximum degree 3and a pair of perfect matchings M1, M2of Gat
distance at most 2on the polytope PG.
Output: A path from M1to M2in the skeleton of PG, of length at most k.
More strongly, for every absolute constant δ > 0, unless the Exponential Time Hypothesis fails,
no polynomial-time algorithm can solve the above problem when kis allowed to grow with the number
Nof vertices of Gas k(N) = j1
4−δlog N
log log Nk.
A path on the perfect matching polytope of a bipartite graph Gis said to be monotone with
respect to some weight vector w= (we)e∈E∈REon the edges of Gif the perfect matchings along
摘要：
展开>>
收起<<
Inapproximabilityofshortestpathsonperfectmatchingpolytopes?JeanCardinal1[0000000223120967]andRaphaelSteiner2[0000000242346136]1UniversitelibredeBruxelles(ULB),Brussels,Belgiumjean.cardinal@ulb.be2ETHZurich,Zurich,Switzerlandraphaelmario.steiner@inf.ethz.chAbstract.Weconsiderthecomputationalproblem...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：15 页
大小：571.62KB
格式：PDF
时间：2025-05-05
渝公网安备50010702506394
