CS614. Advanced Algorithms. L22 Quiz.

CS614. Advanced Algorithms.

L22 Quiz

Back to the course page

Problem 1. Hall Set

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