Is an independent set a biclique?
After figuring out the first reduction from Vertex Cover (VC) described below, I realised that I had assumed that a biclique has at least one vertex in each part (and thus at least one edge). But in many ways it makes more sense to consider an independent set (IS) to be a biclique too: it is a complete bipartite subgraph induced by two disjoint vertex subsets $A$ and $B$ -- it just happens that one of the subsets is empty -- so it (vacuously) meets the criteria. (Similarly, a one-vertex graph is still considered a bipartite graph, and still considered a clique.) I could not quickly find a "standard" definition to confirm either possibility, so I'll first give a reduction that considers only complete induced bipartite subgraphs with both vertex sets nonempty to be bicliques, and then describe how to modify the construction when independent sets are also considered to be bicliques (which turned out to be much trickier).
I'll call the problem in question "Maximal Biclique Hitting Set" (MBHS). A biclique that contains at least one edge (i.e., is not an IS) is an "edgy" biclique.
Reduction from Vertex Cover for "edgy" bicliques
The following construction builds a MBHS instance $(G' = (V', E'), k')$ that replaces every edge in the input graph $G = (V, E)$ with a "rectangle" in which the two pairs of diagonally opposite vertices form a 4-vertex maximal biclique.
Add all vertices and edges in $G$ to $G'$. For every edge $uv$ in $E$, create two new vertices $x_{uv}$ and $y_{uv}$ in $G'$, and the three edges $x_{uv}y_{uv}$, $uy_{uv}$ and $vx_{uv}$. Set $A_{uv} = \{u, x_{uv}\}$ and $B_{uv} = \{v, y_{uv}\}$ and observe that $(A_{uv}, B_{uv})$ forms a biclique with 2 vertices in each part.
To see that this biclique is maximal, consider any other vertex $z \in V' \setminus \{u, v, x_{uv}, y_{uv}\}$. To be able to add $z$ to $A_{uv}$ to form a larger biclique $(A_{uv}', B_{uv})$, $z$ must be adjacent to both $v$ and $y_{uv}$ -- but by construction, the only vertices adjacent to $y_{uv}$ are $x_{uv}$ and $u$, and $z$ is not either of those. Similar reasoning shows that $z$ cannot be added to the other side ($B_{uv}$) either. Since $z$ was arbitrary, $(A_{uv}, B_{uv})$ must be a maximal biclique.
Finally, set the threshold parameter $k'$ for the MBHS instance to $k$. This concludes the construction. I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:
If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k'$. The VC directly gives a solution to the MBHS instance, since every maximal biclique in $G'$ (both the rectangle bicliques that we created, and any bicliques already present in $G$) contains some edge of $G$, and every edge of $G$ contains at least one vertex in the VC solution.
If there is a solution to the constructed MBHS instance of size at most $k'$, then there is a solution to the original VC instance of size at most $k$. Assume there is an edge $uv$ in $G$ whose corresponding edge in $G'$ is not covered (i.e., neither of its endpoint vertices is in the MBHS solution), since otherwise we are already done. Let $(\{u, x_{uv}\}, \{v, y_{uv}\})$ be the unique rectangle maximal biclique that contains $uv$ in $G'$: then it must be that at least one of $x_{uv}$ or $y_{uv}$ is in the MBHS solution, since there is no other way to hit this biclique. Replace whichever one of these two vertices is in the solution (choose arbitrarily if both are) with either $u$ or $v$ (again, choose arbitrarily) to create a new MBHS solution of the same size (at most $k$) with one more $G$-edge covered. This can be repeated until every edge in $G$ is covered by a vertex in the MBHS solution, which remains of size at most $k$. Finally, discard any remaining "rectangle vertices" (vertices not in $V$) from the solution, leaving a VC of size at most $k$.
When independent sets are considered bicliques too
If independent sets are also bicliques, the construction above can fail, most obviously on a graph containing vertices but no edges (which has a single maximal biclique, but an empty VC).
Create $|V|+1$ copies of $G'$ (that is, of the graph constructed for the reduction for edgy maximal bicliques). Call this new graph $G''$. The key observation is that in $G''$, there are $|V|+1$ copies of each maximal edgy biclique in $G'$ that all need to be hit separately, but a set of vertices that hits every maximal IS in a single copy of $G'$ suffices to hit every maximal IS in $G''$. (There are actually vastly more maximal ISes in $G''$ than in $G'$, since to form a maximal IS in $G''$, we may independently choose a maximal IS from each copy of $G'$. But an IS in $G''$ cannot be maximal unless it includes some $G''$-IS in each copy -- so it suffices to choose a particular copy and hit every maximal IS in that copy.)
Let $k''$ be the threshold parameter that together with $G''$ forms the constructed instance of MBHS. Set $k'' = k(|V|+1) + |V|$. Essentially this allows us to spend $k$ vertices hitting edgy maximal bicliques in each of the $|V|+1$ copies of $G'$, plus up to $|V|$ vertices to hit maximal ISes.
That ends the description of the construction. I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:
If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k''$. To see this, first replicate the VC solution across all $|V|+1$ copies of $G'$ in $G''$: these vertices hit every edgy maximal biclique for a cost of $k(|V|+1)$. Now add every remaining vertex from the first copy of $G'$ to the solution, ensuring that we hit every maximal IS in that copy of $G'$, and thus every maximal IS in $G''$ overall, for at most $|V|$ more vertices. Every maximal biclique is now hit and we have used at most $k(|V|+1) + |V| = k''$ vertices.
If there is a solution to the constructed MBHS instance of size at most $k''$, then there is a solution to the original VC instance of size at most $k$. By the pigeonhole principle, at least one of the $|V|+1$ copies of $G'$ has at most $k$ vertices in the solution. These $k$ vertices necessarily hit all edgy maximal bicliques in that copy, since there is no other way to hit these bicliques, and so can be transformed into a solution to the original VC instance of size at most $k$ in the same way as described earlier for the "edgy bicliques" version of the reduction.
Obviously all steps can be carried out in polynomial time, so the MBHS problem is NP-hard. (It's not clear to me that it is in NP though -- there could be exponentially many maximal ISes (consider a $3n$-vertex graph consisting of $n$ vertex-disjoint triangles), so checking that each one is hit takes too long. Does anyone have thoughts on a certificate that can be checked in poly-time?)
Bonus material: A failed reduction attempt
My first attempt at dealing with non-edgy bicliques was to add one new vertex $p$ to $G'$, and connect it to every other vertex in $G'$: Now every maximal independent set originally in $G'$ becomes a maximal biclique with $p$ on one side, and intuitively it seems that it would be a good idea to include $p$ in the MBHS solution, as it would hit every such biclique for the cost of just 1 vertex. The problem is that it could be that every maximal IS in $G'$ is already hit by some vertex in the VC, meaning that it is not actually necessary to include $p$, and that doing so would therefore yield a suboptimal solution. (This can happen when the given threshold $k$ is loose; in particular, it will always happen for $k=|V|$. If OTOH $k$ is the minimal threshold for which the answer to the VC problem is YES, then at least one maximal IS misses every vertex in the VC solution, and we would be justified in forcing $p$ into the solution -- but we don't know whether this is the case at the point when we are mapping the VC instance to the MBHS instance, and it is NP-hard to find out!) The general approach here, of trying to design a gadget that will cause all ISes in $G'$ to become edgy bicliques, can be expressed precisely as: Find a small graph that has an optimal MBHS solution with the additional property that every maximal IS in the graph is hit by some vertex in the solution. But after trying several examples with 2, 3 or 4 vertices, I wasn't able to come up with such a gadget.
