NP-complete? Optimal graph embedding for a graph with certain restrictions

Question

I have a grid graph where nodes and edges occupy cells. The edges may intersect but cannot move one above the other in the same direction.

Suppose I want to optimize a graph to minimize the distance covered by the edges. I am currently using A * search for each connection, but the algorithm is greedy and does not plan ahead. Consider the diagram below, in which the order in which the connections are made changes (note also that for any given edge there can be several shortest paths, see Green and Purple Connections).

My intuition says it is NP-Complete and an exhaustive search is needed, which will be extremely expensive as the size of the chart grows. However, I can’t show this, and it’s not exactly the same as other graph embedding problems that usually involve minimizing intersection.

Answer 1

You did not describe your problem and your image disappeared, but your problem sounds like a minimal problem with T-join.

The minimal T-join problem is defined on the graph G. You get a set T of even size, and you are trying to find a subgraph of the graph where the vertices of T have an odd degree and the other vertices have an even degree. You have weights at the edges, and you are trying to minimize the sum of the weights of the edges in the subgraph.

Surprisingly, the minimal problem of T-union can be solved in polynomial time due to the very close connection with the problem of nonemptiness. Namely, if you find the shortest paths of all pairs between the vertices of T, the minimum T-connection is achieved by the minimum weight of the perfect match of the vertices in T, where there is an edge between two vertices whose length is the length of the shortest path in G.

The minimum T-connection will be a set of paths. If two different paths, say a-> b and c-> d, use the same edge uv, then they can be replaced by a-> u-> c and b-> v-> d and reduce the cost T - join. Therefore, he will not use the same edge twice.