Computing the intersection of all (minimal) vertex covers 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$.
 A: 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:

*

*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.

*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)$.
