5
$\begingroup$

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.

Original Graph

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:

Solution without color constraint

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:

Attempt with color constraint

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?

$\endgroup$
  • 2
    $\begingroup$ If that's not NP-complete, I'll buy an edible hat and eat it. $\endgroup$ – David Richerby May 28 '16 at 2:38
  • $\begingroup$ @D.W. Thanks for the feedback. This means that the primary objective is to maximize X. If there are multiple such solutions, then Y should be maximized as a "first tiebreaker". If there are also multiple such solutions then Z should be maximized as "second tiebreaker". How could I better formulate this? $\endgroup$ – Adama May 28 '16 at 12:22
  • $\begingroup$ @Adama, that's a great way to say it! $\endgroup$ – D.W. May 28 '16 at 14:32
  • $\begingroup$ @DavidRicherby A prerequisite for NP-completeness is to be able to verify a given solution in polynomial time. I don't currently see how that could be applicable here; if the problem was find a set of vertex-disjoint cycles that cover at least $K$ colors a solution would be verifiable in polynomial time. $\endgroup$ – Adama May 28 '16 at 17:40
  • $\begingroup$ @Adama Oops. Should have said NP-hard. $\endgroup$ – David Richerby May 28 '16 at 17:58
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very clear explanation, thank you! Are you aware of published approximation algorithms? Googling "barter exchange approximation" or "Tropical Exchange approximation" didn't help. $\endgroup$ – Adama Jun 18 '18 at 17:37
  • $\begingroup$ Only the trivial $j$-approximation in the above paper, when the problem input is restricted to at most $j$ vertices of each color. $\endgroup$ – tjhighley Sep 14 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.