2023/11/01 by Cardinal, Jean, Steiner, Raphael · 1 citation
#05B35 #05C50 #05C65 #52B40 #90C05 #90C08 #90C27 #90C35 #90C49 #90C57 #90C60 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2311.00779
Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form ei - ej. We consider the following computational problem: Given two vertices of a generalized permutohedron P, find a shortest path between them on the skeleton of P. This captures many known flip distance problems, such as computing the minimum number of exchanges between two spanning trees of a graph, the rotation distance between binary search trees, the flip distance between acyclic orientations of a graph, or rectangulations of a square. We prove that this problem is NP-hard, even when restricted to very simple polymatroids in ℝn defined by O(n) inequalities. Assuming P\not= NP, this rules out the existence of an efficient simplex pivoting rule that performs a minimum number of nondegenerate pivoting steps to an optimal solution of a linear program, even when the latter defines a polymatroid. We also prove that the shortest path problem is inapproximable when the polymatroid is specified via an evaluation oracle for a corresponding submodular function, strengthening a recent result by Ito et al. (ICALP'23). More precisely, we prove the APX-hardness of the shortest path problem when the polymatroid is a hypergraphic polytope, whose vertices are in bijection with acyclic orientations of a given hypergraph. The shortest path problem then amounts to computing the flip distance between two acyclic orientations of a hypergraph. On the positive side, we provide a polynomial-time approximation algorithm for the problem of computing the flip distance between two acyclic orientations of a hypergraph, where the approximation factor is the maximum codegree of the hypergraph. Our result implies an exact polynomial-time algorithm for the flip distance between two acyclic orientations of any linear hypergraph.