Skip to main content
2 of 2
added 101 characters in body
domotorp
  • 19k
  • 3
  • 58
  • 127

This answer is incorrect! As pointed out by Ben, I confused dominating set and vertex cover.

Yes, it is true. For every vertex $v$ of the hypergraph $\pi$, consider the edges of the graph $G$ that run between hyperedges that intersect in $v$. This will be a clique, which we can denote by $K_v$. We can select any vertex of the clique for each $v$, this gives a vertex cover of size at most "$\ell$".

The linearity seems not needed. It would imply, btw, that any two such cliques are edge-disjoint, that is, $K_v\cap K_u\cap E=\emptyset$. Therefore in this case the edgeset of the graph, $E$, is an edge-disjoint union of cliques.

domotorp
  • 19k
  • 3
  • 58
  • 127