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?