[Solved]: Is the weighted transitive reduction problem NP-hard?

Problem Detail: 

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$.

When $E^t \subseteq E$ it is NP-complete. When $E^t \subseteq V\times V$ but not necessarily of $E$, this problem is polynomial time solvable. I am wondering about the edge-weighted version without the subset requirement.

My initial feeling was that with weights, the problem is very similar to TSP. The greedy approach seems to be invalid when adding weights. But several articles (http://bioinformatics.oxfordjournals.org/content/26/17/2160.short for instance) seems to imply that the problem is solvable in polynomial time.

If it was easy, then you could just add arbitrarily large edge weights to each edge not in the original edge set and keep the weights at unity for the others. Then you would have a polynomial time algorithm for the subset constrained problem.

So this should mean it HAS to be NP, right?

edit: Are there immidiate examples that come to mind of problems whose unweighted version is easy, but gets hard when weights are added?

edit: by edge-weighted, I mean we are interested in finding the graph with the smallest total edge cost

Asked By : Benjamin Lindqvist

Answered By : Benjamin Lindqvist

Consider $G=(V,E)$. Let $w_{ij} = 1$ if $e_{ij} \in E$ and let $w_{ij} \gg 1$ if $e_{ij} \notin E$. This choice of weights correspond exactly to the constraint $E' \subseteq E$. Thus, if the weighted transitive reduction is polynomial time solvable, then so is the minimum equivalent graph problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40472

3.2K people like this

 Download Related Notes/Documents