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?

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.