6
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The problem is equivalent to the 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .