Brute$-$force Algorithm for the decision version of Maximum Acyclic Subgraph Problem.

$[20$points$]$ In the decision version of Maximum Acyclic Subgraph Problem we are given a simple

directed graph $G=(V,E)$ and a number $k$ and we are asked to determine if there is a subset

$E^{\text{'}}$subeE such that $G^{\text{'}}=(V,E^{\text{'}})$ is cycle free and $|E^{\text{'}}|=|E|-k.$ The decision version of the problem

is known to be $NP-$complete. Give brute force algorithm for this problem

a$.(5$ pts$)$ What is a certificate for the decision version of the problem?

b$.(5$ pts$)$ What is a verifier for the problem?

c$.(5$ pts$)$ How do we generate all certificates for the problem?

d$.(5$ pts$)$ What is the run$-$time of your algorithm?