An algorithm for covert back-to-back ticketing

Airline booking ploys are ways to circumventing airlines ticket rules in order to spend less on the ticket. We consider a special case, the back-to-back ticketing/nested ticketing. TripSavvy has a good article on back-to-back ticketing.

For many airlines, back-to-back ticketing is explicitly forbidden, this includes American Airlines, Delta and United.

We want to model back-to-back ticketing into an algorithmic problem. There is a sequence of trips between two locations, and it can be grouped into different round trips. Each round trip itinerary has a different cost. A round trip itinerary is no more than a matching between two trips.

This can be seen as simple matching problem. The vertices are trips, which we can assume a trip means “traveling from A to B on date x”. There is an edge between two trips, if there is a round trip itinerary containing the trips. The cost of the edge is the cost of buying a round trip for those two trips. Since it is also possible that we buy a one-way ticket, there are also self-loops. Also, we can consider a multigraph, where the edges are colored. Each color class represents an airline.

If one does not care about the airline finding out, it is just a minimum weight perfect matching problem allowing self-loops. However, people might actually care about airline not happy about this practice. Hence we are interested in making sure in each airline, we have no overlapping itineraries. However, we do allow overlapping itineraries across airlines.

For two edges $\left\{a,b\right\}$ and $\left\{c,d\right\}$ defined over integers, it is independent if $[a,b]\cap [c,d]=\varnothing$. A set of edges is independent if the edges are pairwise independent.

I suspect for arbitrary $k$, the problem is NP-hard. We show how to solve the problem in polynomial time for $k=2$.

Yizhi Song stated the idea that if one edge in a color is picked, it forces some edges of the other color to be picked. We can use the idea to obtain an $O(n^3)$ time algorithm for this problem.

Since we are only working with $k=2$ case, we will let $\bar{a}$ to be the color that is not $a$. Recall $[n]=\left\{1,\dots ,n\right\}$ and $[a..b]=\left\{a,a+1,\dots ,b\right\}$. We assume the vertices $V=[n]$. For a graph with $k$ color classes, we define $G_a$ to be the subgraph consists of all edges of color $a$. $c_a(x,y)$ is the cost of a color $a$ edge $xy$. We define $D(a,y,z)$ as the optimal solution when the input graph is $G_{\bar{a}}[[z-1]\setminus \left\{y\right\}]\cup G_a[[y-1]]$. Intuitively, this is the optimal solution where we need to match all vertices in $Z=[z-1]\setminus \left\{y\right\}$, but can only use $a$ colored that is fully contained in $[y-1]$, and $\bar{a}$ colored edges fully contained $Z$. We also define $C_a(x,y)$ to be the optimal solution when the input graph is $G_a[[x..y]]$. Namely, a min-cost perfect matching covering all vertices $[x..y]$ but we can only use $a$ colored edges contained in $[x..y]$.

The optimal solution is $D(a,n+1,n+1)$ for either color $a$.

We express the recursive relation. For $y<z$, we have the following. $$D(a,y,z)=\min \{\begin{array}{l}{\min }_{x<y}\left\{C_{\bar{a}}(y+2,z-1)+c_{\bar{a}}(x,y+1)+D(\bar{a},x,y)\right\}\\ C_{\bar{a}}(y+1,z-1)+D(\bar{a},y,y)\end{array}$$ It might be beneficial to see the intuition behind the two cases through the following pictures.

On the other hand, when $y=z$ $$D(a,y,y)=\underset{x<y}{\min }\left\{D(a,x,y)+c_a(x,y),D(\bar{a},x,y)+c_{\bar{a}}(x,y)\right\}$$ One can easily infer the base case through definition. Note that all values of $C_a$ can be computed in $O(n^2)$ time. It takes $O(n)$ time to compute one value in $D$. Therefore, the total running time is $O(n^3)$.

One can show that even with $k$ different airlines, there is an algorithm with running time $O(n^{O(k)})$.