3
$\begingroup$

Would appreciate any insight about the following regarding set covers:

Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\bigcup S = X$. Consider the task of finding all inclusion-minimal covers of $X$. (Covers are inclusion-minimal if the removal of any subset $s_i$ from the cover destroys its coverage property.)

Given the set of inclusion-minimal covers $C=\{c_1, c_2, ... c_m\}$, what is an upper bound for $\max|c_i|$, that is, the largest inclusion-minimal cover? It seems fairly straightforward to show that one upper bound is $|X|$ (that is, an inclusion-minimal cover will contain at most the same number of subsets as there are elements in $X$ itself).

But can a better bound be found?

Additional information: No restrictions are assumed for $S$. The bound would ideally be expressed in terms of one or more properties of $S$ (in whatever form those might take).

A conjecture: If $\min |s_i| = k$, then $\max |c_i|$ (the size of the largest inclusion-minimal cover) is bounded above by $|X| - k + 1$. This is based upon two observations:

(1) In constructing any inclusion-minimal cover, we start with any element from $S$ (call it $s_{1'}$). As $s_{1'}$ covers a particular subset of elements from $X$, the next added cover element (call it $s_{2'}$) must cover at least one new element from $X$ not covered by $s_{1'}$.

(2) If $\min |s_i| = k$, then we can choose the first element $s_{1'}$ in our cover to have size $k$. This leaves $|X| - k$ elements in $X$ left uncovered. By the first observation, each additional $s_i$ must cover at least one new element in $X$, so we can add at most $|X| - k$ additional elements to the cover, leading to a cover size at most $|X| - k + 1$.

As noted in the comments, this type of bound might not be significantly smaller than $|X|$ itself. However, I am hoping to use this in a combinatorial context, so any savings helps. Even smaller bounds would still be useful.

$\endgroup$
  • 1
    $\begingroup$ What parameters do you want the bound to be in terms of? Certainly it's at most $|X|$ and at most $|S|$. Is there some other parameter of particular interest? $\endgroup$ – D.W. Jan 4 at 3:21
  • $\begingroup$ both bounds from @D.W. are tight. An example is $S:=\{\{x\};x \in X\}$. $\endgroup$ – narek Bojikian Jan 4 at 3:23
  • $\begingroup$ It might be an interesting question to find such a bound when the sets in $S$ have a fixed size. However, in the current formulation you can't say much about the bounds. $\endgroup$ – narek Bojikian Jan 4 at 3:28
  • $\begingroup$ @D.W. It would have to based on some property of $S$ (or the individual $s_i$) but I wouldn't know how to be more specific than that at this point. For instance, perhaps it's the case that if we have $|s_i| \geq 2$ for all $i$, (that is, there are no subsets that contain only a single element from $X$) then the bound is actually less than $|X|$. $\endgroup$ – Robert Rovetti Jan 4 at 5:19
  • $\begingroup$ @narekBojikian The sets in $S$ are not necessarily constrained to have a fixed size, although that is an interesting sub-case. I'd hope that whatever computation for the bound would be based on exactly those sorts of properties about $S$ (for instance, if the size of the sets in $S$ are themselves bounded, does that allow us to say something about the bound of $\max |c_i|$. $\endgroup$ – Robert Rovetti Jan 4 at 5:24
2
$\begingroup$

The trivial bounds are that $|c| \le |X|=n$ and $|c| \le |S|=p$.

Knowing bounds on the sizes of the sets $s_i$ doesn't help much. For instance, consider the family of sets $s_1,\dots,s_{n-k+1}$ given by $s_i=\{i,n-k+2,\dots,n-1,n\}$. These sets are all of size $k$, and yet the largest inclusion-minimal cover has size $n-k+1$, i.e., exactly equal to the trivial bound of $|S|$ and fairly close to the trivial bound of $|X|$. So, knowing only the sizes of the sets does not help to provide upper bounds that are much better than the trivial ones.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ With the $|S|$ in this example, it appears that $|S| = n-k+1$, which is equivalent to the value of the trivial bound $|S|=p$....unless I'm reading this wrong? $\endgroup$ – Robert Rovetti Jan 4 at 20:10
  • $\begingroup$ @RobertRovetti, good point, see my edited answer for clarification. Thanks for helping me improve my answer. $\endgroup$ – D.W. Jan 4 at 20:55
  • $\begingroup$ @DW, Yes, and thank you for your great example, it has actually led me to formulate a conjecture which I may add to the original question above. $\endgroup$ – Robert Rovetti Jan 5 at 0:39

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.