Lower bounding the minimum equivalent graph

Question

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?

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.