Lower bounding the minimum equivalent graph

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?

• 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? – D.W. Mar 17 '15 at 6:37
• 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. – Benjamin Lindqvist Mar 17 '15 at 11:09
• The other question is re: the WEIGHTED transitive reduction, this question is about the unweighted case. – Benjamin Lindqvist Mar 17 '15 at 11:11

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.