The Weighted Sitting Closer to Friends than Enemies Problem in the Line
share
The weighted Sitting Closer to Friends than Enemies (SCFE) problem is to find an injection of the vertex set of a given weighted graph into a given metric space so that, for every pair of incident edges with different weight, the end vertices of the heavier edge are closer than the end vertices of the lighter edge. In this work, we provide a characterization of the set of weighted graphs with an injection in R that satisfies the restrictions of the weighted SCFE problem. Indeed, given a weighted graph G, we define a polyhedron M(G)x≤b, and show that a weighted graph G has an injection that solves the weighted SCFE problem in R if and only if M(G)x≤b is not empty. As a consequence of this result, we conclude that deciding the existence of, and constructing such an injection for a given complete weighted graph can be done in polynomial time. On the other hand, we show that deciding if an incomplete weighted graph has such an injection in R is NP-Complete. Nevertheless, we prove that if the number of missing edges is constant, such decision can be done in polynomial time.
READ FULL TEXT