0
$\begingroup$

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

Improve this question
$\endgroup$
10
  • $\begingroup$ I'm actually going to post a related, more general question which I will link here when I'm done. $\endgroup$
    – Benjamin Lindqvist
    Commented Mar 16, 2015 at 12:49
  • $\begingroup$ cs.stackexchange.com/questions/40475/… - It's not the same question but it is related... $\endgroup$
    – Benjamin Lindqvist
    Commented Mar 16, 2015 at 13:13
  • 1
    $\begingroup$ I can't tell what you are asking. What is your question? Are you asking whether it is in NP? whether it is NP-hard? It looks like you have some basic confusions about the definitions. What do you mean by "when ...?" Those are two different problems; which one are you asking about? Note that if the unweighted version is NP-hard, the weighted version is, too (as the unweighted version is a special case). Your question is not at all clear -- please edit. (Also, why isn't this a duplicate of cs.stackexchange.com/q/40475/755?) $\endgroup$
    – D.W. ♦
    Commented Mar 17, 2015 at 6:37
  • $\begingroup$ "When $E^t\subseteq E$ it is NP-complete. When $E^t\subseteq V\times V$". $E^t$ is a minimum-weight relation whose transitive closure includes $E$ so $E^t$ is always a subset of $E$. The edge relation of a graph is always a set of pairs of vertices. $\endgroup$
    – David Richerby
    Commented Mar 17, 2015 at 9:07
  • $\begingroup$ @DavidRicherby What? In the transitive reduction problem you're free to add edges that wasn't in the original graph. E isn't the closure, it's the original edge set. $\endgroup$
    – Benjamin Lindqvist
    Commented Mar 17, 2015 at 11:05

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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