Set of vertex-disjoint cycles maximizing different colored vertices

Question

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$.

I am looking to find a set of vertex-disjoint cycles that:

1. First maximizes the number of differently colored covered vertices.
2. In case of ties, break ties by secondly maximizing the number of chosen edges.
3. In case of any further ties, third minimizes the total cost of the chosen edges.

This is very similar to this problem, with additional constraint (#1). Without the first constraint (maximize the colors) this problem is easily solved by:

• Splitting each vertex $v$ to $v^+$ and $v^-$.
• Each vertex $v^+$ and $v^-$ provides a supply of $+1$ and $-1$, respectively.
• Replacing an original edge $e': v \to w$ with $e: v^+ \to w^-$. Such each edge has cost $cost(e') = cost(e)$ and unit capacity.
• Adding a "bind" edge $e'' : v^+ \to v^-$. Its cost is $c(e'') \gg 1$

Here is a representation:

And the problem has been reduced to a minimum-flow problem (MCF). A MCF algorithm will choose $A_1 \to B_1 \to A_2 \to B2 \to A_3 \to B_3 \to A_1$.

My question: is it possible to apply a similar modeling to satisfy the color constraint in polynomial time? If so, is it possible to reduce the problem to a MCF problem?

Here is how far I have managed to take it:

Here, bind-edges $e''$ go through a collective set of nodes, one per color, e.g., "A no+" and "A no-". These represent the corresponding vertices not chosen. Between "A no+" and "A no-" three edges are added with unit capacities and costs $ c(e_{red}) >> c(e_{orange}) >> 1$

I basically model that the cost of not choosing one or even two yellow items is insignificant to the cost of not choosing all three yellow items. Therefore, the goal is to choose $A_1 \to C \to B_3 \to A_1$.

Nevertheless, this did not quite work. Basically, if a flow goes through $A_1^+ \to A_{no}^+ \to A_{no}^-$, it's not guaranteed that it will return to $A_1^-$.

I have tried other approaches, including toying around with non-unit capacities, but I didn't find a solution. Can it be solved in polynomial time?

Answer 1

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP.

Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature and can be solved in polynomial time with a reduction to the Assignment Problem.

With the introduction of colors to the problem, it is NP-hard (and the corresponding decision problem is NP-complete). The problem that you described can be called TROPICAL MAX SIZE EXCHANGE (TROPMAX EXCHANGE). CNFSAT reduces to TROPMAX EXCHANGE.

Create a graph with one vertex for each variable in the CNFSAT expression, with all of these "variable vertices" colored the same way. Assign each clause in the expression its own color. From each "variable vertex" create two cycles - label one cycle 'true' and one 'false'. For each literal in the expression, create a vertex that is the color of its clause and put it on the appropriate 'true' or 'false' cycle of the corresponding variable vertex. Finally, add additional vertices of some new color so that every 'true' and 'false' cycle has the same number of vertices.

Because we are choosing vertex-disjoint cycles, each 'variable vertex' can only be in its 'true' cycle or 'false' cycle, not both. There are no cycles in the graph other than those true/false cycles. Every cycle has the same number of vertices, so an algorithm that first maximizes the number of vertices in the cycles can choose any combination of cycles: either true or false for each variable vertex. If the secondary criterion is to maximize the number of colors in the cycles, then if all colors can be included the CNFSAT expression can be satisfied.

Highley, Timothy and Le, Hoang. "Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent" dmtcs:3186 - Discrete Mathematics & Theoretical Computer Science, July 31, 2018, vol. 20 no. 2 https://dmtcs.episciences.org/4690 https://arxiv.org/abs/1610.05115