The hardness of routing two pairs on one face

Details The hardness of routing two pairs on one face The hardness of routing two pairs on one face

2009-11-16

arxiv.org/abs/0911.3024v1

Computer Science

Discrete Mathematics

Scientific paper

We prove the NP-completeness of the integer multiflow problem in planar graphs, with the following restrictions: there are only two demand edges, both lying on the infinite face of the routing graph. This was one of the open challenges concerning disjoint paths, explicitly asked by M\"uller. It also strengthens Schw\"arzler's recent proof of one of the open problems of Schrijver's book, about the complexity of the edge-disjoint paths problem with terminals on the outer boundary of a planar graph. We also give a directed acyclic reduction. This proves that the arc-disjoint paths problem is NP-complete in directed acyclic graphs, even with only two demand arcs.

Affiliated with

Also associated with

No associations

Rating

The hardness of routing two pairs on one face does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The hardness of routing two pairs on one face, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hardness of routing two pairs on one face will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499221