Fault-Tolerant Matroid Bases

A linear matroid over a field $𝔽$ can be represented by a set of vectors $\{{𝐯}_1,\mathrm{\dots },{𝐯}_m\}$ in a vector space $𝒱\subseteq {𝔽}^d$. The rank of the matroid corresponds to $dim(𝒱)$. A basis here is simply a set of $d$ linearly independent vectors. A set of vectors $\{{𝐮}_1,\mathrm{\dots },{𝐮}_r\}$ is $k$-fault-tolerant if, after removing up to $k$ vectors, the remaining set still spans the entire subspace $𝒱$. Such concepts naturally arise in distributed storage – where vectors might be stored on different servers [11] – and in coding theory, where losing some symbols or vectors should not destroy the ability to recover the entire space [13].

For a connected graph $G$, its graphic matroid $ℳ(G)$ has ground set $E(G)$, and a set $I\subseteq E(G)$ is independent if it forms a forest. A basis is thus a spanning tree of $G$. In this matroid, a set of edges $B\subseteq E(G)$ is $k$-fault-tolerant if, upon removing any $k$ edges, the subgraph remains connected. Thus, a $k$-fault-tolerant basis is a $(k+1)$-edge connected spanning subgraph with minimum number of edges. This problem is known in the literature as $k$-Edge-Connected Spanning Subgraph [8, 14, 17]. It is motivated by network applications as its task is to compute a minimum-cost sub-network that is resilient against up to $k$ link failures (see also [5]).

A gammoid is derived from a directed (or undirected) graph $D$. Let $X$ and $Y$ be two distinguished sets of vertices of $V(D)$. Within the set $X$, define a subset $U\subseteq X$ to be independent if there exist $|U|$ vertex-disjoint paths in $G$ originating from vertices in $Y$ and ending in the vertices of $U$. The basis of the gammoid is the maximum set of vertices from $X$ that can be reached by vertex-disjoint paths from $Y$. In this case, a vertex set $Z\subseteq X$ is a $k$-fault-tolerant basis if upon removing any $k$ vertices from $Z$, the remaining vertices are still linkable from sources in $Y$ without losing rank. This problem is related to the problem of finding fault-tolerant disjoint paths studied by Adjiashvili et al. [1].

A transversal matroid $ℳ(U,𝒮)$ is described via a bipartite graph between a ground set $U$ and a set of “target positions” $𝒮$. A set $I\subseteq U$ is independent if it can be matched injectively to distinct elements in $𝒮$. The basis of the transversal matroid is a maximum-size subset $I\subseteq U$ that can be perfectly matched into $𝒮$. Finding a $k$-fault-tolerant basis for a transversal matroids is naturally related to robust matching problems, where one wants to preserve a perfect (or maximum) matching under the loss of a few vertices or edges [12, 18].

The lower bound immediately follows from the definition of a $k$-fault-tolerant basis. To show the upper bound, assume for the sake of contradiction that $|B|>(k+1)\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$. We iteratively construct sets $X_0,\mathrm{\dots },X_k$ where $X_0\subseteq B$ is an inclusion-maximal independent set in $B$, and for each $i\in \{1,\mathrm{\dots },k\}$, $X_i$ is an inclusion-maximal independent set in $B\setminus \left({\bigcup }_{j=0}^{i-1}{X}_j\right)$. Since $\mathrm{𝗋𝖺𝗇𝗄}(B)=\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$ and $|B|>(k+1)\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$, such sets $X_0,\mathrm{\dots },X_k$ exist. Set $B^{\prime }={\bigcup }_{i=0}^k{X}_i$. Consider an arbitrary $F\subseteq B$ of size at most $k$. By the pigeonhole principle, there is an index $i\in \{0,\mathrm{\dots },k\}$ such that $X_i\cap F=\mathrm{\varnothing }$. By construction, it holds that $B\setminus B^{\prime }\subseteq B\setminus \left({\bigcup }_{j=0}^{i-1}{X}_j\right)\subseteq \mathrm{𝖼𝗅}(X_i)$. Hence, $B\setminus F\subseteq (B^{\prime }\setminus F)\cup (B\setminus B^{\prime })\subseteq \mathrm{𝖼𝗅}(B^{\prime }\setminus F)$. Because $B$ is a $k$-fault-tolerant basis, $\mathrm{𝖼𝗅}(B\setminus F)=E(ℳ)$. Thus,

Since $F$ was chosen arbitrarily, we obtain that $B^{\prime }$ is a $k$-fault-tolerant basis of $ℳ$. However, since , this contradicts the choice of $B$. $◀$

We next argue that the bounds in Proposition 6 are tight. First, note that the lower bound is tight as the matroid $ℐ(ℳ)=\{X\subseteq E(ℳ):|X|\le k\}$ proves. We next argue that the upper bound is also tight. Let $e_1,\mathrm{\dots },e_r$ be a basis of ${ℝ}^r$. Let $k$ and $n$ be integers such that . Consider the linear matroid $ℳ$ with $E(ℳ)=\{j{e}_i\mid 1\le i\le r\text{ and }1\le j\le n\}$. It is easy to see that any $k$-fault-tolerant basis of $ℳ$ has to contain at least $k+1$ vectors of $\{j{e}_i\mid 1\le j\le n\}$ for each $i\in \{1,\mathrm{\dots },r\}$. Thus, the size of a $k$-fault-tolerant basis is at least $(k+1)r$. From the other side, we have that, for $B=\{j{e}_i\mid 1\le i\le r\text{ and }1\le j\le k+1\}$, $\mathrm{𝗋𝖺𝗇𝗄}(B\setminus F)=r$ for any $F\subseteq E(ℳ)$ of size at most $k$. Thus, $B$ is a $k$-fault-tolerant basis of size $(k+1)r$ of $ℳ$.

Let $ℳ$ be a matroid. For a positive integer $h$, we say that a set $X\subseteq E(ℳ)$ is $h$-uniform if $\mathrm{𝗋𝖺𝗇𝗄}(X)=h$ and $\mathrm{𝗋𝖺𝗇𝗄}(Y)=h$ for every subset $Y\subseteq X$ of size $h$. The definition and Proposition 6 yield the following.

If $B$ is a $k$-fault-tolerant basis, then, for every set $F\subseteq B$ of size at most $k$, $\mathrm{𝗋𝖺𝗇𝗄}(B\setminus F)=r$. Since $|B|=k+r$, this implies that, for every set $X\subseteq B$ of size $r$, $\mathrm{𝗋𝖺𝗇𝗄}(X)=\mathrm{𝗋𝖺𝗇𝗄}(B)=r$, that is, $B$ is $r$-uniform. For the opposite direction, if $B$ is $r$-uniform, then, for any $X\subseteq B$ of size $r$, $\mathrm{𝗋𝖺𝗇𝗄}(X)=\mathrm{𝗋𝖺𝗇𝗄}(B)=\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$. Since $|B|=k+r$, it holds for any $F\subseteq B$ of size at most $k$ that $\mathrm{𝗋𝖺𝗇𝗄}(B\setminus F)=\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$. This completes the proof. $◀$

We conclude this section by proving Proposition 2 using the results of Fomin et al. [15]. In particular, they studied Rank $h$-Reduction. Here, the input is a binary matroid $ℳ$ given by its representation over $\mathrm{𝖦𝖥}[2]$ and two positive integers $h$ and $k$. The task is to decide whether there is a set $X\subseteq E(ℳ)$ of size at most $k$ such that $\mathrm{𝗋𝖺𝗇𝗄}(ℳ)-\mathrm{𝗋𝖺𝗇𝗄}(ℳ-X)\ge h$.

We reduce from Rank $h$-Reduction parameterized by $k$, which is known to be W[1]-hard [15]. Let $(ℳ,h,k)$ be an instance of Rank $h$-Reduction where $ℳ$ is a binary matroid of rank $r$. We define ${ℳ}^{\prime }$ to be the $(r-h+1)$-truncation of $ℳ$. Notice that ${ℳ}^{\prime }$ is a linear matroid and its representation (over a different field) can be constructed in polynomial time by the result of Lokshtanov et al. [20]. We claim that ${ℳ}^{\prime }$ has no $k$-fault-tolerant basis if and only if $(ℳ,h,k)$ is a yes-instance of Rank $h$-Reduction.

To this end, note that ${ℳ}^{\prime }$ has no $k$-fault-tolerant basis if and only if there is a set $X\subseteq E({ℳ}^{\prime })$ of size at most $k$ such that . Since if and only if $\mathrm{𝗋𝖺𝗇𝗄}(ℳ)-\mathrm{𝗋𝖺𝗇𝗄}(ℳ-X)\ge h$, ${ℳ}^{\prime }$ has no $k$-fault-tolerant basis if and only if there is $X\subseteq E({ℳ}^{\prime })$ of size at most $k$ such that $\mathrm{𝗋𝖺𝗇𝗄}(ℳ)-\mathrm{𝗋𝖺𝗇𝗄}(ℳ-X)\ge h$. This concludes the proof. $◀$

We remark that since the hardness for Rank $h$-Reduction was proven by Fomin et al. [15] via a polynomial-time reduction from Clique, it is $\mathrm{coNP}$-hard to decide whether a linear matroid has a $k$-fault-tolerant basis. We also note that the problem is in XP since we can decide in $n^{𝒪(k)}$ time whether an $n$-element matroid $ℳ$ has a $k$-fault-tolerant basis – simply check for each subset $X\subseteq E(ℳ)$ of size $k$ whether $\mathrm{𝗋𝖺𝗇𝗄}(ℳ-X)=\mathrm{𝗋𝖺𝗇𝗄}(ℳ)$.

Let $B$ be a $k$-fault-tolerant basis of $ℳ$. If $B\subseteq \mathrm{𝖼𝗅}(X)$, then the claim is straightforward because in this case, $\mathrm{𝖼𝗅}(X)=E(ℳ)$ and $r=h$. We can therefore select $B^{\prime }$ to be the set of $k+r$ arbitrary elements of $X$ by Observation 7. We hence assume from now on that $B\setminus \mathrm{𝖼𝗅}(X)\ne \mathrm{\varnothing }$.

Consider a $k$-fault-tolerant basis $B^{\prime }$ satisfying (i), that is, $B\setminus \mathrm{𝖼𝗅}(X)=B^{\prime }\setminus \mathrm{𝖼𝗅}(X)$, such that the size of $B^{\prime }\cap (\mathrm{𝖼𝗅}(X)\setminus X)$ is minimum. We claim that $B^{\prime }$ satisfies (ii), that is, $B^{\prime }\cap \mathrm{𝖼𝗅}(X)\subseteq X$. Assume towards a contradiction that $B^{\prime }\cap (\mathrm{𝖼𝗅}(X)\setminus X)\ne \mathrm{\varnothing }$ and there is an element $x\in B^{\prime }\cap (\mathrm{𝖼𝗅}(X)\setminus X)$. Let $Y=B^{\prime }\setminus \{x\}$. Note that $Y$ is not a $k$-fault-tolerant basis of $ℳ$. Hence, there is a set $F\subseteq Y$ of size at most $k$ such that . Notice that $\mathrm{𝗋𝖺𝗇𝗄}(B^{\prime }\setminus F)=r$ implies $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r-1$. Denote by $ℱ$ the family of all sets $F\subseteq Y$ of size at most $k$ such that $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r-1$. For each $F\in ℱ$, let $Z_F\subseteq Y$ be an inclusion-maximal independent set in $Y\setminus F$ and let $𝒵=\{Z_F\mid F\in ℱ\}$. Note that $\mathrm{𝖼𝗅}(Z_F)=\mathrm{𝖼𝗅}(Y\setminus F)$ and therefore $\mathrm{𝗋𝖺𝗇𝗄}(Z_F)=r-1$ for each $F\in ℱ$. By Proposition 6, it holds that $|Y|\le (k+1)r-1$. Hence, $|𝒵|\le \left(\genfrac{}{}{0pt}{}{(k+1)r-1}{r-1}\right)\le {[(k+1)r]}^{r-1}$. We next show that $|\mathrm{𝖼𝗅}(Z_F)\cap X|\le h-1$ for each $F\in ℱ$.

To this end, assume towards a contradiction that $|\mathrm{𝖼𝗅}(Z_F)\cap X|\ge h$. Since $X$ is $h$-uniform, we obtain that $X\subseteq \mathrm{𝖼𝗅}(\mathrm{𝖼𝗅}(Z_F)\cap X)$. Then $\mathrm{𝖼𝗅}(X)\subseteq \mathrm{𝖼𝗅}(\mathrm{𝖼𝗅}(Z_F)\cap X)\subseteq \mathrm{𝖼𝗅}(Z_F)$ and, in particular, $x\in \mathrm{𝖼𝗅}(Z_F)=\mathrm{𝖼𝗅}(Y\setminus F)$. However, in this case, $B^{\prime }\setminus F=(Y\cup \{x\})\setminus F\subseteq \mathrm{𝖼𝗅}(Y\setminus F)$. Since $B^{\prime }$ is a $k$-fault-tolerant basis, we have that $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=\mathrm{𝗋𝖺𝗇𝗄}(B^{\prime }\setminus F)=r$ contradicting $F\in ℱ$.

Recall that $|X|\ge (h-1){[(k+1)r]}^{r-1}+(k+1)r$ and $B^{\prime }$ has at least one element outside $X$. Then, $|B^{\prime }|\le (k+1)r$ and therefore $|X\setminus B^{\prime }|\ge (h-1){[(k+1)r]}^{r-1}+1$ by Proposition 6. Since and, for each $F\in ℱ$, $|\mathrm{𝖼𝗅}(Z_F)\cap X|\le h-1$, a simple counting argument shows that there exists an element $y\in X\setminus B^{\prime }$ such that $y\notin \mathrm{𝖼𝗅}(Z_F)$ for all $F\in ℱ$. Let $B^{\ast }=Y\cup \{y\}=(B^{\prime }\setminus \{x\})\cup \{y\}$. Note that by definition, (i) $B^{\ast }\setminus \mathrm{𝖼𝗅}(X)=B^{\prime }\setminus \mathrm{𝖼𝗅}(X)$, (ii) , and (iii) $|B^{\ast }|=|B^{\prime }|$. We next show that $B^{\ast }$ is a $k$-fault-tolerant basis. Afterwards, we will show that this contradicts our choice of $B^{\prime }$.

Towards the former, let $F\subseteq B^{\ast }$ be of size at most $k$. We prove that $\mathrm{𝗋𝖺𝗇𝗄}(B^{\ast }\setminus F)=r$. If $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r$, then $\mathrm{𝗋𝖺𝗇𝗄}(B^{\ast }\setminus F)\ge \mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r$. So we assume from now on that . Then, $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r-1$ as shown above. Assume towards a contradiction that $y\in F$. Since $y\notin B^{\prime }$, we have that $F^{\prime }=(F\setminus \{y\})\cup \{x\}$ is a subset of $B^{\prime }$ of size at most $k$. Since $B^{\prime }$ is a $k$-fault-tolerant basis, $\mathrm{𝗋𝖺𝗇𝗄}(B^{\prime }\setminus F^{\prime })=r$. However, $B^{\prime }\setminus F^{\prime }=Y\setminus F$ and $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r$, contradicting our assumption that . Hence, $y\notin F$ and therefore $F\subseteq Y$. Recall that $\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r-1$. This implies that $F\in ℱ$ and $Z_F\in 𝒵$. Since $y\notin \mathrm{𝖼𝗅}(Z_F)$ by the choice of $y$, $\mathrm{𝗋𝖺𝗇𝗄}(B^{\ast }\setminus F)=\mathrm{𝗋𝖺𝗇𝗄}((Y\setminus F)\cup \{y\})>\mathrm{𝗋𝖺𝗇𝗄}(Y\setminus F)=r-1$. Thus, $\mathrm{𝗋𝖺𝗇𝗄}(B^{\ast }\setminus F)=r$.

Since $\mathrm{𝗋𝖺𝗇𝗄}(B^{\ast }\setminus F)=r$ for every $F\subseteq B^{\ast }$ of size at most $k$ and $|B^{\ast }|=|B^{\prime }|$, we have that $B^{\ast }$ is a $k$-fault-tolerant basis. However, we also obtain that (i) $B^{\ast }\setminus \mathrm{𝖼𝗅}(X)=B^{\prime }\setminus \mathrm{𝖼𝗅}(X)$ and (ii) contradicting the choice of $B^{\prime }$. This shows that $B^{\prime }\cap \mathrm{𝖼𝗅}(X)\subseteq X$ and completes the proof. $◀$

Now we show how to construct a set $W$ of important elements of bounded size.

Let $ℳ$ be a matroid of rank $r\ge 1$ such that $\{e\}\in ℐ(ℳ)$ for any $e\in E(ℳ)$ and let $k$ be a non-negative integer. We construct a recursive branching algorithm $\text{Important}(ℳ,X)$ that takes as input a matroid $ℳ$ and a non-empty independent set $X\in ℐ(ℳ)$, and outputs a set $Y\subseteq \mathrm{𝖼𝗅}(X)$ of size at most ${|X|}^{{|X|}^2}\cdot {[(k+1)r]}^{r{|X|}^2}$ with the property that for any $k$-fault-tolerant basis $B$ of $ℳ$, there is a $k$-fault-tolerant basis $B^{\prime }$ such that

1. (i)

   $B\setminus \mathrm{𝖼𝗅}(X)=B^{\prime }\setminus \mathrm{𝖼𝗅}(X)$ and

2. (ii)

   $B^{\prime }\cap \mathrm{𝖼𝗅}(X)\subseteq Y$.

Let $h=|X|$. The base case is $h=1$, where we do the following:

• $\mathrm{■}$

  Compute $\mathrm{𝖼𝗅}(X)$.

• $\mathrm{■}$

  If , then set $Y:=\mathrm{𝖼𝗅}(X)$ and output it.

• $\mathrm{■}$

  Otherwise, define $Y$ to be the set of $(k+1)r$ arbitrary elements of $\mathrm{𝖼𝗅}(X)$ and output it.

For $h>1$, we do the following:

• $\mathrm{■}$

  Compute $\mathrm{𝖼𝗅}(X)$.

• $\mathrm{■}$

  If $|\mathrm{𝖼𝗅}(X)|\le (h-1){[(k+1)r]}^{r-1}+(k+1)r$, then set $Y:=\mathrm{𝖼𝗅}(X)$, output it, and stop.

• $\mathrm{■}$

  Find a $h$-uniform set $Z\subseteq \mathrm{𝖼𝗅}(X)$ that either has size $(h-1){[(k+1)r]}^{r-1}+(k+1)r$ or is an inclusion-maximal $h$-uniform set of size at most $(h-1){[(k+1)r]}^{r-1}+(k+1)r-1$.

• $\mathrm{■}$

  If $|Z|=(h-1){[(k+1)r]}^{r-1}+(k+1)r$, then set $Y:=Z$ and output it.

• $\mathrm{■}$

  If $Z$ is an inclusion-maximal $h$-uniform set of size at most $(h-1){[(k+1)r]}^{r-1}+(k+1)r-1$, then output $Y:={\bigcup }_{S\subseteq Z\text{ s.t. }|S|=h-1}{Y}_S$, where $Y_S$ is the output of $\text{Important}(ℳ,S)$.

To compute an $h$-uniform set $Z$, we apply the following greedy procedure:

• $\mathrm{■}$

  Initially, set $Z:=X$.

• $\mathrm{■}$

  While $Z\le (h-1){[(k+1)r]}^{r-1}+(k+1)r-1$, do the following:

  • –

    For every $x\in \mathrm{𝖼𝗅}(X)\setminus Z$, check whether $Z\cup \{x\}$ is $h$-uniform and set $Z:=Z\cup \{x\}$ if this holds.

  • –

    If $Z\cup \{x\}$ is not $h$-uniform for all $x\in \mathrm{𝖼𝗅}(X)\setminus Z$, then output $Z$ and stop.

• $\mathrm{■}$

  If $Z=(h-1){[(k+1)r]}^{r-1}+(k+1)r$, then output $Z$.

The crucial property of the algorithm is given in the following claim whose proof combines Lemma 8 and induction on $h$. Here and further, the proofs of the statements labeled ($\star$) are omited in this extended abstract and can be found in the full version of the paper [4].

It remains to analyze the size of $Y$ and the running time. We next show an upper bound on the size of $Y$ of $|Y|\le h^{h^2}\cdot {[(k+1)r]}^{r{h}^2}$. We prove this via induction on $h$.

For $h=1$, note that $|Y|\le (k+1)r\le h^{h^2}\cdot {[(k+1)r]}^{r{h}^2}$. For $h\ge 2$, consider any independent set $S\subseteq E(ℳ)$ of size $h-1$. The algorithm outputs the set $Y_S$, which by the induction hypothesis, has size at most $N_{h-1}={(h-1)}^{{(h-1)}^2}{[(k+1)r]}^{r{(h-1)}^2}$. By construction, we have

Observe first that

For the second option, note that

Combining this equation with Equation 1, we obtain the required upper bound for $|Y|$.

Finally, we evaluate the running time of Important and show that $\text{Important}(ℳ,X)$ runs in ${(rk)}^{𝒪(r{h}^2)}\cdot n^{𝒪(1)}$ time. To this end, notice that $\mathrm{𝖼𝗅}(X)$ can be constructed in polynomial time in the oracle model. To construct the $h$-uniform set $Z$ of size $h{(rk)}^{𝒪(r)}$, we use the greedy procedure where for each $x\in \mathrm{𝖼𝗅}(X)\setminus Z$ for the considered $Z$, we go over all subsets $S$ of $Z$ of size $h-1$ and check whether $S\cup \{x\}$ is independent using the oracle. As $h\le r$, the construction of $Z$ can be done in ${(kr)}^{𝒪(rh)}\cdot n^{𝒪(1)}$ time. The algorithm makes ${(rk)}^{𝒪(rh)}$ recursive calls and the depth of the search tree is at most $h$. Summarizing, we obtain that the overall running time is ${(rk)}^{𝒪(r{h}^2)}\cdot n^{𝒪(1)}$.

To complete the proof and construct $W$, we call $\text{Important}(ℳ,X)$ for an arbitrary basis $X$ of $ℳ$ and set $W=Y$ for the output set of the algorithm. Note that a basis can be found in polynomial time using the independence oracle. Then Claim 10 implies that if $ℳ$ has a $k$-fault-tolerant basis, then it also has one in $W$. Note that the other direction is trivial as $W\subseteq E(ℳ)$. This concludes the proof. $◀$

We are now ready to prove Theorem 1, which we restate here for convenience.

Let $ℳ$ be a matroid of rank $r$ and let $k\ge 0$ be an integer. Fault-Tolerant Basis is trivial for $r=0$ and we can assume that $r\ge 1$. Notice that loops of $ℳ$, that is, elements $e$ such that $\{e\}\notin ℐ(ℳ)$ are irrelevant – a loop $e$ is not included in any $k$-fault-tolerant basis and $e\in \mathrm{𝖼𝗅}(X)$ for any set $X\subseteq E(ℳ)$. Hence, we can preprocess $ℳ$ and delete the loops. From now on, we assume that $\{e\}\in ℐ(ℳ)$ for every $e\in E(ℳ)$.

We apply the algorithm from Lemma 9, and in time ${(rk)}^{𝒪(r^3)}\cdot n^{𝒪(1)}$, find a set $W\subseteq E(ℳ)$ of size at most $r^{r^2}\cdot {[(k+1)r]}^{r^3}$ such that whenever $ℳ$ has a $k$-fault-tolerant basis, $ℳ$ has a $k$-fault-tolerant basis $B\subseteq W$. We consider all candidate subsets $B$ of $W$ with $|B|\le (k+1)r$ using the upper bound for the size of a $k$-fault-tolerant basis from Proposition 6. This can be done in ${(kr)}^{𝒪(k{r}^4)}$ time. For each candidate set $B$ of size at most $(k+1)r$, we verify whether $B$ is a $k$-fault-tolerant basis as follows. In $𝒪({[(k+1)r]}^k)$ time, we check whether $\mathrm{𝗋𝖺𝗇𝗄}(B\setminus F)=r$ for every subset $F\subseteq B$ of size at most $k$. Among all candidate sets satisfying the above property, we select a set of minimum size which is a $k$-fault-tolerant basis of $ℳ$. The overall running time is ${(kr)}^{𝒪(k{r}^4)}\cdot n^{𝒪(1)}$. This concludes the proof. $◀$

To show (i), suppose that $|X|=s(r-1)+k+1$ and $|X\cap P_i|\le s$ for each $i\in \{1,\mathrm{\dots },d\}$ for some integer $s\ge 1$. Consider any subset $F\subseteq X$ of size at most $k$. Since $|X\cap P_i|\le s$ for every $i\in \{1,\mathrm{\dots },d\}$, it holds that $|(X\setminus F)\cap P_i|\le s$ and hence $|(X\setminus F)\cap P_i|>0$ for at least $\lceil \frac{|X\setminus F|}{s}\rceil$ sets $P_i$. Since $ℳ$ is a partition matroid with unit capacities, this is also a lower bound on $\mathrm{𝗋𝖺𝗇𝗄}(X\setminus F)$ and therefore

This proves that $\mathrm{𝗋𝖺𝗇𝗄}(X)\ge r$ and $\mathrm{𝗋𝖺𝗇𝗄}(X\setminus F)\ge r$ for any set $F\subseteq X$ of size at most $k$.

To prove (ii), suppose that $X$ is an inclusion-minimal set with $\mathrm{𝗋𝖺𝗇𝗄}(X)\ge r$ such that for any set $F\subseteq X$ of size at most $k$, $\mathrm{𝗋𝖺𝗇𝗄}(X\setminus F)\ge r$ holds. We assume without loss of generality that $|X\cap P_1|\ge \mathrm{\cdots }\ge |X\cap P_d|$.

If $r=1$, then we set $s=\max \{|X\cap P_i|\mid 1\le i\le d\}$. Trivially, $|X|\ge k+1$ and $|X\cap P_i|\le s$ for every $i\in \{1,\mathrm{\dots },d\}$. We next show that $|X|=k+1$. Assume towards a contradiction that $|X|>k+1$. Any subset $X^{\prime }\subseteq X$ of size $k+1$ satisfies $|X^{\prime }\cap P_i|\le s$ for every $i\in \{1,\mathrm{\dots },d\}$. Hence, $\mathrm{𝗋𝖺𝗇𝗄}(X^{\prime }\setminus F)>1$ for any set $F$ of size at most $k$ by (i). This contradicts the the minimality of $X$ and shows $|X|=k+1$.

If $r\ge 2$, then $|X\cap P_{r-1}|\ge 1$ and we set $s=|X\cap P_{r-1}|$. We will next show that $|X|=s(r-1)+k+1$ and $|X\cap P_i|\le s$ for every $i\in \{1,\mathrm{\dots },d\}$. Let $Y={\bigcup }_{j=1}^{r-1}(X\cap P_j)$ and $Z={\bigcup }_{j=r}^d(X\cap P_j)$. By definition of $s$, $|Y|\ge s(r-1)$.