1
$\begingroup$

I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances. I know that, in general, the complexity of the problem in terms of the number of variables (and computational time) increases with the number of edges in the graph. I also know that for particular graphs where node degree is fixed (for example 3 or 4), polynomial-time algorithms exist that return the optimal solution. Therefore, I am playing around with removing the edges with the highest weight from the graph, while ensuring each node retains at least a minimum degree, and seeing how this impacts solution time. As expected, reducing the number of edges in the graph does impact the solution time significantly.

Are there any theoretical results that tie this idea of removing edges from the graph before solving the problem to the optimality of the solution? Is it in some cases possible to conclude, a-priori, that some specific edge will necessarily NOT be part of the optimal solution?

$\endgroup$
1
$\begingroup$

I don't know anything about routing, so take this with a grain of salt.

What you have is a metric graph, in that your graph satisfies the triangle inequality. If you start removing edges, then heuristic algorithms might have less to work with, which isn't obviously better.

Take for example a look at these questions:


Taking removing edges to the extreme is actually how Christofides algorithm works for approximating Travelling Salesman; Namely by finding a Minimum Spanning Tree and deleting all the remaining edges.

$\endgroup$
5
  • $\begingroup$ Thanks for your response. I was working under the assumption that removing an edge from a metric graph would not make it non-metric. Although I can see that adding an edge can easily drop this property, I'm not sure how removing one can have the same effect. Are you suggesting it might cause problems with the triangle inequality because a distance might not be defined anymore? In other words: does "might no longer be metric" mean that if I ensure I do not cut the graph into separate connected components then I can safely say the graph is still metric? $\endgroup$ May 14 '21 at 14:07
  • $\begingroup$ With triangle inequality, we mean that there is no edge that weighs more than the shortest path from its endpoints. $\endgroup$
    – Pål GD
    May 14 '21 at 14:48
  • $\begingroup$ Ok, I get this, but I do not see how removing and edge from a graph can render this inequality invalid, unless we remove the only edge that connects two different connected components. Then a "shortest path" might cease to exist. Is this what you mean by "If you start removing edges, then the graph might no longer be a metric graph"? $\endgroup$ May 14 '21 at 14:51
  • 1
    $\begingroup$ No, you are right. $\endgroup$
    – Pål GD
    May 14 '21 at 16:00
  • 1
    $\begingroup$ Updated the answer. $\endgroup$
    – Pål GD
    May 14 '21 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.