# Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?

The following problem is from my algorithms class:

Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph induced by $C$. A biclique is called maximal if it is not a subset of a larger biclique. Then our problem asks whether there exists a subset of $V$ of size at most $k$ hitting all maximal bicliques of $G$, i.e., can we find $k$ vertices in $V$ such that every maximal bicliques of $G$ cantains at least one vertex of these $k$ vertices. Prove the problem is NP hard.

I'm trying to prove $$\text{Vertex-Cover} \le_p \text{This-Problem}$$ but haven't came up with a solution until now. Could anyone help me out here?

• One strategy to think about: Is there something you can do to the input graph to make every biclique small? – j_random_hacker May 16 '18 at 7:55
• @j_random_hacker reduce the size of every biclique by half ? – Mengfan Ma May 16 '18 at 8:34
• I now think that was the wrong direction to go. A better direction is to think of a way to change the input graph so that each edge corresponds to a distinct maximal biclique. I don't think I can help you much more than that without giving the game away. – j_random_hacker May 16 '18 at 9:39
• @j_random_hacker I'm now considering a reduction from Hitting-Set problem. It may work ... – Mengfan Ma May 16 '18 at 10:09
• @Mark You can write an answer if you come up with a solution. – xskxzr May 16 '18 at 12:00

## 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.

• If $G$ is a triangle, $G$ has vertex cover of size 2, but I can’t find 2 vertices hitting all maximal bicliques in $G’$. – Mengfan Ma May 25 '18 at 2:10
• I only reviewed the part before "When independent sets are considered bicliques too". Looks OK to me. – xskxzr May 25 '18 at 5:46
• @xskxzr Sorry, I misunderstood it. Looks good to me too. – Mengfan Ma May 25 '18 at 6:45

Transformation from Hitting Set to this problem. In the Hitting Set problem, we are given a collection $C=\{S_i\}$ of subsets of a universal set $U$ and an integer $k$, the question is that if one can choose $k$ elements of $U$ to hit all the subsets. The Hitting Set problem can be described as a bipartite graph $B=(U\cup C,E)$. We may add the following constraint without affecting its NP-completeness: $S_i \not\subseteq S_j$ for any $S_i, S_j\in C$. By this constraint, each $S_i$ and its members form a maximal biclique. On the other hand, a vertex subset hitting all $S_i$ clearly hits all the maximal bicliques. That is, a vertex subset $H$ hits every maximal biclique if and only if $H$ hits every $S_i$ in $C$. To complete the reduction from Hitting Set to this problem, it is easy to show that if there are $k$ vertices in $U\cup C$ hitting all $S_i$, then there are $k$ vertices in $U$ hitting all $S_i$.

• There may be other maximal bicliques, for example, an element and all sets containing it. – xskxzr May 22 '18 at 16:55
• @xskxzr of course there may be other bicliques. But if $H$ hits all $S_i$, it hits all bicliques. – Bangye May 22 '18 at 19:46
• For example, $S_1=\{1,2\},S_2=\{2,3\},S_3=\{3,4\},S_4=\{4,5\}$, then $\{2,4\}$ hits all sets but it does not hit the maximal biclique $\{S_2, S_3, 3\}$. – xskxzr May 23 '18 at 2:50
• @xskxzr you are right. The proof is wrong – Bangye May 23 '18 at 4:25
• I’ve been working on a reduction from Hitting set problem like what you did for days. But as shown in @xskxzr ‘s counter example, it’s impossible to hit all maximal bicliques by only two vertices while there indeed exists a hitting set of size 2. Can we conclude that a construction like this is a wrong way to go? – Mengfan Ma May 23 '18 at 5:07