Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.
We show that it isDP-hard to determine the combinatorial diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question. Abstract Let Qc,r be the integer hull of the intersection of the assignment polytope with a given hyper-plane H = x = (xij) ϵ Rn × n: ∑ni = 1 ∑nj = 1 cijxij = r . We show that the problem of checking whether two given extreme points of Qc,r are nonadjacent on Qc,r is solvable in O (n5) time if c = (cij) is a 0–1 matrix, and that it is NP-Complete if c is a general integer matrix. The (combinatorial) diameter of a polytope P ⊆ ⊆ R^d is the maximum value of a shortest path between a pair of vertices on the 1-skeleton of P, that is the graph where the nodes are given by the 0-dimensional faces of P, and the edges are given the 1-dimensional faces of P. The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, [Frieze and Teng, 1994] showed that computing the diameter of a polytope is (weakly) NP-hard. In this paper, we show that the problem of computing the diameter is strongly NP-hard even for a polytope with a very simple structure: namely, the fractional matching polytope. We also show that computing a pair of vertices at maximum shortest path distance on the 1-skeleton of this polytope is an APX-hard problem. We prove these results by giving an exact characterization of the diameter of the fractional matching polytope, that is of independent interest. We show that the shadow vertex algorithm can be used to compute a short path between a given pair of vertices of a polytope @math along the edges of P, where A∈ℝm ×n. Both, the length of the path and the running time of the algorithm, are polynomial in m, n, and a parameter 1 δ that is a measure for the flatness of the vertices of P. For integer matrices A∈ℤm ×n we show a connection between δ and the largest absolute value Δ of any sub-determinant of A, yielding a bound of O(Δ4mn4) for the length of the computed path. This bound is expressed in the same parameter Δ as the recent non-constructive bound of O(Δ2n4 log(n Δ)) by [1]. For the special case of totally unimodular matrices, the length of the computed path simplifies to O(mn4), which significantly improves the previously best known constructive bound of O(m16n3 log3 (mn)) by Dyer and Frieze [7]. We consider the problem of determining whether two traveling salesman tours correspond to non-adjacent vertices of the convex polytope associated with the traveling salesman problem. This problem is shown to be NP-Complete for both the symmetric and nonsymmetric traveling salesman problem. Several implications are discussed. To each finite set with at least two elements, there corresponds a partial order polytope. It is defined as the convex hull of the characteristic vectors of all partial orders which have that set as ground set. This 0 1-polytope contains the linear ordering polytope as a proper face. The present article deals with the facial structure of partial order polytopes. Our main results are: (i) a proof that the nonadjacency problem on partial order polytopes is NP-complete; (ii) a characterization of the polytopes that are affinely equivalent to a face of some partial order polytope. Abstract In this paper we show that adjacency on the 0–1 knapsack polytope can be determined by a very simple argument. Namely, let u and v be two feasible solutions to the 0–1 knapsack problem, then u and v are nonadjacent on the polytope of the convex hull of feasible solutions, if and only if, there exist two other feasible solutions w 1 and w 2 , such that 1 2w 1 + 1 2w 2 = 1 u + 1 2v . This observation allows us to prove that the question of determining whether two given feasible solutions are adjacent, is an NP-complete problem. In this paper, we discuss the adjacency structures of some classes of 0-1 polytopes including knapsack polytopes, set covering polytopes and 0-1 polytopes represented by complete sets of implicants. We show that for each class of 0-1 polytope, non-adjacency test problems are NP-complete. For equality constrained knapsack polytopes, we can solve adjacency test problems in pseudo polynomial time.