The Art Gallery Guardian

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 MM be a matching of a graph GG where the edges are two colored. MM is called valid if vertex 2i2i and 2i12i-1 are contained in the same colored edge in MM.

Problem1Couple back-to-back ticketing problem

Input: A multigraph G=(V,E)G=(V,E) where V[n]V\subseteq [n], where each edge can be either red or blue, and there is an edge cost function c:ER+c:E\to \R^+.

Output: A valid perfect matching MM (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 ii, we split it into (i,R)(i,R) and (i,B)(i,B) for its blue and red counter part. A matching is paired if (2i,C)(2i,C) and (2i1,C)(2i-1,C) both has to be matched, where C{R,B}C\in \set{R,B}. The matching is split if (i,R)(i,R) and (i,B)(i,B) 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 MM, such that the vertices covered by MM is in some special structure. Namely Δ\Delta-matroid. Since the paired property is a very special Δ\Delta-matroid [1], which was first solved in [2]. The second property is partition matroid, which can be handled by hierarchical bb-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 Δ\Delta-matroid. Naonori Kakimura communicated a more fundamental problem which can be solved by this problem.

Problem2Matching with disjoint pair constraints

Given a graph where the edges are partitioned into pairs. Find a maximum matching where it uses at most one edge of each pair.

I would be very interested to know the solution to that problem.


[1] N. Kakimura, M. Takamatsu, Matching Problems with Delta-Matroid Constraints, SIAM Journal on Discrete Mathematics. 28 (2014) 942–961 10.1137/110860070.

[2] A. Hefner, P. Kleinschmidt, A constrained matching problem, Annals of Operations Research. 57 (1995) 135–145 10.1007/BF02099694.

Posted by Chao Xu on .
Tags: Optimization, algorithm, airline.