In parameterized complexity, $k$-set cover is W[2]-hard. The definition of $k$-set cover is as follows:
Input: A ground set $U$ and a family of sets $\cal{F}$;
Parameter: $k$;
Output: Whether there are at most $k$ sets in $\cal{F}$ covering $U$.
The general $k$-set cover problem is W[2]-hard.
But if the incidence graph is $K_{d,d}$-free for some constant $d$, then the problem is FPT.
($K_{d,d}$ means a complete bipartite graph with $d$ vertices for each part.)
Here the incidence graph is a bipartite graph, where one part, say $A$, has a vertex for each element in $\mathcal{F}$ and the other part, say $B$, has a vertex for each element in $U$ , and there is an edge between $a \in A$ and $u \in B$, if $u$ belongs to the set corresponding to $a$.
The proof of the FPT result only uses the upper bound of the number of edges for $K_{d,d}$-free graphs.
My question is how to find an intuitive point that the $K_{d,d}$-free incidence graph can make the problem easier?
Thanks.
