Long distance couple back-to-back ticketing
The reason I explored an algorithm for covert back-to-back ticketing in the previous blog post, was because as someone currently in a long distance relationship. It is important to save money on travel.
For long distance couples, two people can fly. Consider if the couple decides be together each weekend, one can fly to the city of the other on Friday night, and comes back on Sunday night. Again we can take advantage of the back-to-back ticketing.
Let be a matching of a graph where the edges are two colored. is called valid if vertex and are contained in the same colored edge in .
Input: A multigraph where , where each edge can be either red or blue, and there is an edge cost function .
Output: A valid perfect matching (allowing self-loops), such that the cost is minimized.
Unfortunately, I don’t see how to solve this problem in polynomial time. I could convert this problem to something that might be solved in polynomial time in the future.
Note we can split the vertices. That is, for vertex , we split it into and for its blue and red counter part. A matching is paired if and both has to be matched, where . The matching is split if and cannot be both in the matching.
If we just enforce one property – paired or split – then it is solvable in polynomial time. Indeed, both are matching under restrictions. We are interested in finding a matching , such that the vertices covered by is in some special structure. Namely -matroid. Since the paired property is a very special -matroid [1], which was first solved in [2]. The second property is partition matroid, which can be handled by hierarchical -matching. Reader can see each individual restriction, the problem can be turned into a maximum weight perfect matching.
If we enforce both property, the problem is open. Although the structure is still very special, it is an even -matroid. Naonori Kakimura communicated a more fundamental problem which can be solved by this problem.
Given a graph where the edges are partitioned into pairs. Find a maximum matching where it uses at most one edge of each pair.
This problem can be used to solve special case of rainbow matching. A graph where each edge has a color, a matching is a rainbow matching if every edge in the matching has a different color. It is known that for graphs where each color appears twice, finding a rainbow matching is NP-hard [3]. The couple back-to-back ticketing problem is also NP-hard.