CS614. Advanced Algorithms. L22 Quiz.
CS614. Advanced Algorithms.
L22 Quiz
Given a bipartite graph \(G\) with bipartite classes \(A, B \subseteq V(G)\) and an integer \(k\), the Hall SET problem asks for a Hall set of size at most \(k\), that is, a set \(S \subseteq A\) of size at most \(k\) such that \(|N(S)|<|S|\). Show that HalL SET is W[1]-hard.
Hint: Reduce from Clique. Given a graph \(G\), we construct a bipartite graph where class \(A\) corresponds to the edges of \(G\) and class \(B\) corresponds to the vertices of \(B\); the vertex of \(A\) corresponding to edge \(u v\) of \(G\) is adjacent to the two vertices \(u, v \in B\). Additionally, we introduce a set of \({k \choose 2}-k-1\) vertices into \(B\) and make them adjacent to every vertex of \(A\).
Show that every Hall set of size at most \({k \choose 2}\) has size exactly \({k \choose 2}\) and corresponds to the edges of a \(k\)-clique in \(G\).