I'm writing a paper about a math puzzle and the thing I'm studying ends up equivalent to finding the following parameter of a bipartite graph G with parts X and Y:



> 
> The largest $k$ such that any $k$ vertices in $X$ all have a common neighbor.
> 
> 
> 


I'm trying to figure out if this parameter has a name and if the corresponding decision problem is NP-complete (which I strongly suspect it is). 


My best lead so far has been this restatement of the parameter: the largest $k$ such that a set family is $k$-wise intersecting. But none of the papers I've looked at seem interested in finding $k$ -- generally it is given and other results follow. 


Does anyone know the name of this parameter (if it exists), or if it is NP-complete?



Looking for the name or reference regarding a bipartite graph parameter
The problem is equivalent to the [set cover problem](https://en.wikipedia.org/wiki/Set_cover_problem) and thus NP-hard.


The set formulation you gave is:



> 
> Given a finite set $\mathcal{X}$, a family $\mathcal{F} \subseteq \mathcal{P}(\mathcal{X})$, what is the largest $k$ such that the intersection of every $k$-subset of $\mathcal{F}$ is nonempty?
> 
> 
> 


A decision version of this is:



> 
> Given a finite set $\mathcal{X}$, a family $\mathcal{F} \subseteq \mathcal{P}(\mathcal{X})$, and integer $k$, is there a $k$-subset of $\mathcal{F}$ whose intersection is empty?
> 
> 
> 


Taking the complement of each set in $\mathcal{F}$, we get the decision version of the set cover problem:



> 
> Given a finite set $\mathcal{X}$, a family $\mathcal{F} \subseteq \mathcal{P}(\mathcal{X})$, and integer $k$, is there a $k$-subset of $\mathcal{F}$ whose union is $\mathcal{F}$?
> 
> 
> 




---


In a similar fashion, we can take the complement (of only edges between $X$ and $Y$) in the graph formulation, and then $k+1$ is the minimum number of vertices in $X$ needed to cover $Y$. But after a quick search I couldn't find this kind of covering number used in literature.


