Computing the intersection of all (minimal) vertex covers

Question

Let $t<n$ be two integers and $G$ an undirected, irreflexive graph without multi-edges of size $n$.

How hard is it to compute the intersection of all (minimal) vertex covers of cardinality $ \leq t$? Or alternatively, how hard is it to compute the intersection's cardinality?

Note: Obviously, the intersection of all vertex covers ($\leq t$) is equal to the intersection of all minimal vertex covers ($\leq t$), hence the parenthesis.

I was wondering whether the hardness of this particular problem has been studied in the literature. Is it efficiently computable, maybe reducible to the MVC-problem or completely unknown?

For $t \leq n-1$ the naive approach would be to consider all subsets of cardinality $t$ and intersect all those which are vertex covers. However this approach would require the consideration of $\binom{n}{t}$ subsets; which is efficient (polynomial in $n$) if and only if $t$ or $n-t$ is bounded by a constant.

Edit: To see that it suffices to intersect only all subset of size equal $t$ instead of all subsets at most $t$, one can write: $$ \begin{equation}\begin{aligned} \bigcap_{i} VC_i^{t} = \bigcap_{i} MVC_i^{t} \cap \bigcap_{i} NMVC_i^{t} \end{aligned}\end{equation} $$ where $MVC^{t}$ denotes a minimal VC of size $t$ and $NMVC^{t}$ denotes a non-minimal VC. Further a NMVC can be split into an MVC of size $t'< t$ and an extension $E^{t-t'}$, hence

$$ \begin{equation}\begin{aligned} \bigcap_{i} VC_i^{t} &= \bigcap_{i} MVC_i^{t} \cap \bigcap_{i} \left(MVC_{i'}^{t'} \cup E_{i'j'}^{t-t'}\right) \\ &= \bigcap_{i} MVC_i^{t} \cap \bigcap_{i'} \underbrace{\bigcap_{j'} \left(MVC_{i'}^{t'} \cup E_{i'j'}^{t-t'}\right)}_{MVC_{i'}^{t'}} \\ &= \bigcap_{i} MVC_i^{t} \cap \bigcap_{i'} MVC_{i'}^{t'} \end{aligned}\end{equation} $$ which is the intersection of all MVCs of size at most $t$. Note that the last equality only holds if there exist at least two disjoint extensions of $MVC_{i'}^{t'}$. This is true for $t' < n-2$ and hence for $t \leq n - 1$ because $t' < t$.

Answer 1

In turns out, there is a reduction from the decision Minimum VC (MinVC) problem, i.e. deciding whether a graph G has a MinVC of size $\leq k$, to the intersecting MVC problem (IMVC) as follows:

hasMVC(G, k):
G' := copy(G);
X := {};
while !isVC(G,X) do
    removeIsolatedNodes(G');
    X' := {};
    t := 0;
    while X' = {} do
        if t < |G'| then
            X' := findIMVC(G', t);
        else
            X' := X' ∪ {P_next};
        endif
        t := t + 1;
    endwhile
    X := X ∪ X';
    G' := G' \ X';
    if |X| > k then
        return false;
    endif
endwhile
return true;

where findIMVC is an oracle function to solve the IMVC problem, $P_{\mathrm{next}}$ is the first vertex of $G'$ in some arbitrary canonical order (e.g. lexicographical or even random) and removeIsolatedNodes is the obvious subroutine for removing vertices without neighbors from $G'$.

Correctness: Intuitively, the outer loop checks whether a candidate vertex set $X$ is a vertex cover of admissible size (<= t), if so, it terminates. Otherwise, it tries to find new vertices $X'$ to add to the set $X$ to make it into a MinVC. The inner loop has two cases:

1. If $t \geq |G'|$, then $G'$ does not contain any IMVC of any size, hence there is a set of MinVCs, say $\{MinVC_1, ..., MinVC_m\}$, such that their intersection is empty. Because the graph $G'$ is connected (via removeIsolatedNode) for each vertex $v$ there is a MinVC that contains $v$. Otherwise, if there was a vertex in no $MinVC_i$, then the neighbors of $v$, which must exists by connectivity, would have to be in all $MinVC_i$; in contradiction to the case condition that the IMVC is empty. Therefore adding any vertex $v$ to $X'$ is valid.
2. If $t < |G'|$, then $t$ is incremented and $G'$ checked for IMVCs of size at most $t$. If one exists, it is added to $X'$ since it is in all MVCs of $G'$. Otherwise repeat the inner loop.

After finding new vertices $X'$ for $X$, the counter $t$ is reset. This fashion of adding only vertices to the candidate set $X$ ensures that the candidates set eventually only contains vertices from a single MinVC. If the size of the (minimal) candidate set $X$ exceeds $k$, then return $false$ since any MinVC of $G$ must then have size at least $|X| > k$.

Runtime: In each outer loop the size of $X$ is increased by at least one because $X' \neq \emptyset$. Thus there are at most $n$ (number of vertices) outer iterations. The inner loop increments $t$ at most until $t = |G'| \leq n$, hence there are at most $n$ inner iterations. The subroutines isVC and removeIsolatedNodes have linear runtime in $n$. So overall, we get a crude runtime bound of $\mathcal{O}(n^2)$.