The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$.

The minimum equivalent graph $G' = (V,E')$ is the smallest graph with the same reachability as $G$ with the property $E' \subseteq E$.

Consider the case when $G$ is strongly connected.

The transitive reduction is formed by an arbitrary Hamiltonian cycle, so $|E^t| \equiv |V|$ and so we must have $|E'| \geq |V|$. We want to find a polynomial time algorithm which finds a tighter lower bound than $|V|$ for $|E'|$. I'm wondering if this is possible at all, assuming $P \neq NP$.

If $|E'|>|V|$, then $G$ can not contain a Hamiltonian cycle . So if we can find a tighter bound in polynomial time, then we have determined the existence of a Hamiltonian cycle in polynomial time.

I think this means that efficiently lower bounding this problem is a wild goose chase. The best bound we can consistently hope for is $|V|$.

Is this a too pessimistic interpretation?

  • $\begingroup$ At cs.stackexchange.com/q/40472/755 you claim that the answer to this question is that the problem is NP-hard. Have you answered your own question? What's the remaining question? $\endgroup$
    – D.W.
    Mar 17, 2015 at 6:37
  • $\begingroup$ The MEG is NP-hard, the transitive reduction is easy. But the number of edges in the MEG solution is always lower bounded by the TR-solution. It seems I'm not expressing myself clearly, but I'm not sure where the misunderstanding lies... I want to know if it's theoretically possible to consistantly find better lower bounds for MEG, given that finding a lower bound better than N means we've determined the existance of a Hamiltonian cycle. $\endgroup$ Mar 17, 2015 at 11:09
  • $\begingroup$ The other question is re: the WEIGHTED transitive reduction, this question is about the unweighted case. $\endgroup$ Mar 17, 2015 at 11:11

1 Answer 1


Yes it's too pessimistic. If by 'consistently', we mean we will deduce the existance/non-existance of a hamilatonian cycle a $1-\epsilon$ fraction of the time but will get an incorrect answer the rest of the time, we STILL haven't found a polynomial time algorithm that guarantees coming to the correct conclusion. So it isn't theoretically impossible to 'consistently' lower bound this problem.


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.