18) Consider the following two computational problems.

MIN-EQUIVALENT DIAGRAM Instance: A directed graph G=(V,E) and an integer k<=|E| question: Is there a directed graph G=(V,E)such that E E,|E|<=K,and such that for every pair of vertices u and v in V,G contains a directed path from u to v if and only if G contains a directed path from u to v?

HAM CIRCUITS FOR STRONGLY CONNECTED DIAGRAPHS Instances: Given a strongly connected directed graph G. question: Does G have a Hamiltonian circuit? Show that MIN-EQUIVALENT-DIAGRAPH is NP-complete assuming HAM CIRCUITS FOR STRONGLY CONNECTED DIAGRAPHS is NP-complete. Recall that a directed graph is strongly connected if there is a directed path for every ordered pair of vertices.