Inapproximability of shortest paths on perfect matching polytopes Jean Cardinal10000000223120967and Raphael Steiner20000000242346136

2025-05-05 0 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 ﬁnding 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 reconﬁguration

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 ﬁrst 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 deﬁning 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 ﬁnd 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

ﬁnd 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 ﬁnding 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 ﬁne-grained complexity program [38]. As a

consequence, there is not much hope of ﬁnding 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 deﬁne 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.

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 deﬁned 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 ﬁnding 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 diﬀerence 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 ﬂipping 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 ﬂipping at most kalternating cycles.

. . .

Fig. 1. Two perfect matchings at distance two on the perfect matching polytope, but whose symmetric

diﬀerence 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 diﬀerence consists of an arbitrary number of cycles.

Our main result is the following.

Theorem 1. Let k≥2be any ﬁxed 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) = j1

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

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Inapproximabilityofshortestpathsonperfectmatchingpolytopes?JeanCardinal1[0000000223120967]andRaphaelSteiner2[0000000242346136]1UniversitelibredeBruxelles(ULB),Brussels,Belgiumjean.cardinal@ulb.be2ETHZurich,Zurich,Switzerlandraphaelmario.steiner@inf.ethz.chAbstract.Weconsiderthecomputationalproblem...

展开>> 收起<<

Inapproximability of shortest paths on perfect matching polytopes Jean Cardinal10000000223120967and Raphael Steiner20000000242346136.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Inapproximability of shortest paths on perfect matching polytopes Jean Cardinal10000000223120967and Raphael Steiner20000000242346136

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: