Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This problem is a following up question on this one. The only difference is the newly added constraint in the bold font.

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$ $$\text{s.t.} x_{ij}+x_{ik} \le 1 $$ $$x_{ij}+x_{jk} \le 1 $$

Note this problem is not the Maximum Weighted Matching problem as edges that share the same end point are allowed.

share|cite|improve this question
up vote 9 down vote accepted

This is easy to solve in polynomial time.

To see this, it may be easiest to interpret $S$ as a preorder $\le$ on $N$:

  • $i \le j$ iff $(i,j) \in S$ or $i = j$.

Then we define the equivalence relation $\sim$:

  • $i \sim j$ iff $i \le j$ and $j \le i$.

Now let $W$ consist of all equivalence classes of $\sim$; for each $i \in N$ let $[i] \in W$ be its equivalence class. Put otherwise, $[i]$ consists of all $j \in N$ such that $(j,i) \in S$ and $(i,j) \in S$. Now we can define the natural partial order $\le'$ on $W$:

  • $[i] \le' [j]$ iff $i \le j$ for each $i,j \in N$.

We say that $[i] \in W$ is maximal if $[i] \le' [j]$ implies $[i] = [j]$. We have the following property that is easy to verify:

  • If $[i]$ is maximal, we cannot get the benefit $c(j)$ for all $j \in [i]$.

Hence in any solution, for every maximal class $[i]$, we have to choose at least one node $j \in [i]$ such that we do not get the benefit of $c(j)$.

We now construct a solution as follows: For each maximal class $[i]$, choose a node $j \in [i]$ that minimises $c(j)$; we say that $j$ is a sink node. Now assume that $k \in N$ is not a sink node. There are too cases:

  • $k \in [i]$, where $[i]$ is maximal. Now we can simply choose the edge $(k,j) \in S$, where $j \in [i]$ is a sink node, and collect the benefit of $c(k)$.

  • $k \in [i]$, where $[i]$ is not maximal. Then there is a maximal set $[\ell]$ with $[i] \le [\ell]$. Let $j \in [\ell]$ be the sink node, choose the edge $(k,j) \in S$, and collect the benefit of $c(k)$.

That is, we can get the benefit of $c(k)$ for all nodes $k \in N$ that are not sink nodes; the solution is optimal.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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