Proof.

1. The \(k\)-norm of \(\mathcal{C}^V\) is \[\begin{align} \sum_{C\in\mathcal{C}^V} \min(|C|,k) &= \sum_{C\in \{\{v\} \mid v \in V\setminus V(\mathcal{C})\}} \min(|C|,k) + \sum_{C\in\mathcal{C}} \min(|C|,k)\\ &= |V\setminus V(\mathcal{C})| + k|\mathcal{C}| \\ &= |V\setminus V(\mathcal{P})| + k|\mathcal{P}| \end{align}\] And thus equal to the \(Sk\)-norm of \(\mathcal{P}\).

2. The \(k\)-norm of \(\mathcal{A}^V\) is \[\begin{align} \sum_{A\in\mathcal{A}^V} \min(|A|,k) &= \sum_{A\in \{\{v\} \mid v \in V\setminus V(\mathcal{A})\}} \min(|A|,k) + \sum_{A\in\mathcal{A}} \min(|A|,k)\\ &= |V\setminus V(\mathcal{A})| + k|\mathcal{A}| \end{align}\]

3. It follows by the previous point and [thm:GK,thm:GKCollections], by noting that \(|A|\ge k\) for all \(A\in \mathcal{A}\) (removing short, \(|A|<k\), antichains decreases the \(Sk\)-norm).

 ◻

Proof. We build the \(\alpha_k\) network (see 2) and compute a minimum cost circulation \(f\) in \(E^{1+o(1)}\) time [19], [20]. Circulation \(f\) can be decomposed into a collection of \(|f|\) paths \(\mathcal{P}_f\) (for solving MPS-\(k\)) or \(|f|\) disjoint chains \(\mathcal{C}_f\) such that \(V(\mathcal{P}_f) = V(\mathcal{C}_f)\) (for solving MCP-\(k\)). By construction (see discussion above 2), the cost of \(f\) is \(c(f) = -|V(\mathcal{P}_f)| + k|\mathcal{P}_f|\), since \(f\) minimizes this cost it also minimizes \(|V\setminus V(\mathcal{P})| + k|\mathcal{P}|\), and thus \(\mathcal{P}_f\) is a MPS-\(k\). We decompose \(f\) into \(\mathcal{P}_f\) in \(O(|E| + \texttt{output})\) time [13], [37]. We can get \(\mathcal{C}_f\) from \(f\) in \(O(|E|\log{|f|}) = O(|E|\log{|V|}) = |E|^{1+o(1)}\) time [6]. In [6], it is additionally stated that \(\mathcal{C}_f\) can be obtained from \(\mathcal{P}_f\) by removing the repeated vertices (up to one copy) from the paths of \(\mathcal{P}_f\). In other words, there is a one-to-one correspondence between \(\mathcal{C}_f\) and \(\mathcal{P}_f\) such that \(C \in \mathcal{C}_f\) is a subsequence of its corresponding \(P \in \mathcal{P}_f\). Next, we note that for every \(P\in \mathcal{P}_f\), \(c_P := |P\setminus V(\mathcal{P}_f \setminus \{P\})| \ge k\); indeed, if \(c_P < k\) then the \(Sk\)-norm of \(\mathcal{P}_f \setminus \{P\}\) is \(k-c_P\) units smaller than the \(Sk\)-norm of \(\mathcal{P}_f\), a contradiction. Moreover, since also \(V(\mathcal{C}_f) = V(\mathcal{P}_f)\), the corresponding \(C \in \mathcal{C}_f\) to \(P\) must cover at least those \(c_P\) vertices, and thus for every \(C \in \mathcal{C}_f, |C| \ge c_P \ge k\). As such, the \(k\)-norm of \(\mathcal{C}_f^V\) is exactly the \(Sk\)-norm of \(\mathcal{P}_f\), by [lem:relations], and thus \(\mathcal{C}_f^V\) is a MCP-\(k\). ◻

Proof. We build the \(\beta_k\) network (see 2) and compute a minimum cost circulation \(f\) in \(E^{1+o(1)}\) time [19], [20]. Circulation \(f\) can be decomposed into a collection of \(|f|\) paths \(\mathcal{P}_f\) (for solving MP-\(k\)) or \(|f|\) disjoint chains \(\mathcal{C}_f\) such that \(V(\mathcal{P}_f) = V(\mathcal{C}_f)\) (for solving MC-\(k\)). By construction (see discussion in 2), the cost of \(f\) is \(c(f) = -|V(\mathcal{P}_f)|\), since \(f\) minimizes this cost, \(\mathcal{P}_f\) is a MP-\(k\) and \(\mathcal{C}_f\) is a MC-\(k\). We decompose \(f\) into \(\mathcal{P}_f\) in \(O(|E|+\texttt{output})\) time [13], [37] and into \(\mathcal{C}_f\) in \(O(|E|\log{|f|}) = O(|E|\log{|V|}) = E^{1+o(1)}\) time [6]. ◻

Proof. Since there are no negative cost cycles in the residual \(G'_f\), the function \(d: V' \to \mathbb{Z}\) such that \(d(v')\) is the distance of a shortest (minimum cost) path from \(s\) to \(v'\) in \(G'_f\), is well defined. In fact, we can compute \(d\) in \(\tilde{O}(|E|)\) by using [21]–[24]. The proof of [thm:GKCollections] defines \(U_i := \{v' \in V' \mid d(v') \ge i + d(t)\}\) and \(A_i = \{v\in V\mid v^{in} \in U'_i \land v^{out} \not\in U'_i\}\) for every \(i\in\{1,\ldots d(s)-d(t)\}\). The proof moreover shows that \(\mathcal{A}_f = \{A_1, \ldots, A_{d(s)-d(t)}\}\) is a collection of antichains and that it is a MA-\(k\) in the \(\alpha_k\) network and a MAS-\(k\) in the \(\beta_k\) network. Note that \(A_i\) corresponds to the set of vertices \(v\in V\) such that \(d(v^{in}) \ge i + d(t)\) and \(d(v^{out}) < i + d(t)\). In particular, if \(d(v^{in}) > d(v^{out})\), then \(v \in A_j\) for \(j \in \{d(v^{out}) - d(t) + 1, \ldots, d(v^{in})-d(t)\}\). As such, we can build \(\mathcal{A}_f\) in \(O(|E|)\) time by checking each edge \((v^{in}, v^{out})\) and placing \(v\) in one such corresponding antichain (e.g. in \(A_{d(v^{in})-d(t)}\)) when \(d(v^{in}) > d(v^{out})\). By [lem:relations], \(\mathcal{A}^V\) is a MAP-\(k\). ◻

Proof. Compute a minimum cost circulation \(f\) in the \(\alpha_k\) network (resp. \(\beta_k\) network) in \(|E|^{1+o(1)}\) time [19], [20], and use 4 to obtain a MA-\(k\) (resp. MAS-\(k\) and MAP-\(k\)). ◻

Proof of [thm:almostLinear]. Combine [lem:almostLinear1,lem:almostLinear2,lem:almostLinear3]. ◻

Proof. We define the following weighted set cover instance: the sets are the chains of \(G\), and for a chain \(C\) its weight is \(\min{(|C|, k)}\). Note that a feasible solution for this weighted set cover instance is a chain cover (not necessarily partition), and its weight corresponds to its \(k\)-norm. As such, MCP-\(k\)’s are optimal solutions to this problem. Moreover, greedy is a \(\ln{|V|}\) approximation [10]. We next show how to compute such a greedy solution efficiently. For this, recall that greedy at each step, chooses the chain \(C\) minimizing the ratio \(w(C)/|U \cap C| = \min{(|C|, k)}/|U \cap C|\), where \(U\) is the set of uncovered vertices. First, note that there is always a chain \(C \subseteq U\) minimizing this ratio, and thus we assume \(C \subseteq U\), and the task becomes to find a chain \(C \subseteq U\) minimizing the ratio \(\min{(|C|, k)}/|C|\). Note that this also ensures that the chain collection found by greedy is a chain partition. Second, if there is no chain \(C \subseteq U\) with \(|C| > k\), then the ratio is always one and any such chain minimizes the ratio, when greedy reaches this point it can just output every vertex in \(U\) in a separated singleton path. Otherwise, greedy must find a chain \(C\subseteq U\) minimizing \(k/|C|\), but since \(k\) is a constant for this minimization, it is equivalent to finding a chain \(C \subseteq U\) maximizing \(|C|\). Such a chain can be obtained by finding a path covering the most vertices from \(U\). Mäkinen et al. [9] show how to compute such a path in \(O(|E|)\) time. Since we stop greedy as soon as there is no chain \(C \subseteq U\) with \(|C| > k\), the running time of our approach is the number of chains \(|C| > k\) times \(O(|E|)\). Finally, since each chain \(|C| > k\) contributes \(k\) to the \(k\)-norm \(O(\alpha_k \log{|V|})\) of the output cover, the number of such chains is \(O(\alpha_k \log{|V|}/k)\). Note that the \(Sk\)-norm of the set of paths and the \(k\)-norm of the chain partition output by greedy is the same, by [lem:relations]. ◻

Proof. We use 5 to compute a collection of paths \(\mathcal{P}\) whose \(Sk\)-norm is at most \(\alpha_k \ln{|V|}\) in \(\tilde{O}(\alpha_k|E|)\) time. These paths correspond to a circulation \(f\) in the \(\alpha_k\) network. The cost \(f\) of this circulation is then \(c(f) = -|V(\mathcal{P})| + k|\mathcal{P}| \le \alpha_k\ln{|V|} - |V|\), and since the minimum cost of a circulation is \(\alpha_k - |V|\) we can use 1 to obtain a minimum cost circulation in \(\tilde{O}(\alpha_k |E|)\) time. As in the proof of [lem:almostLinear2], we can obtain a MCP-\(k\) and a MPS-\(k\) from the minimum cost flow circulation (output size for MPS-\(k\) is \(O(\alpha_k|E|)\)). We use 4 to obtain a MA-\(k\). ◻

Proof of [thm:nearLinear]. Combine [lem:nearLinear1,lem:nearLinear2]. ◻

Proof. For \(U = V\), the well-known reduction to minimum flow corresponds to \(G'\) as in Schrijver’s reduction but without the edge \((t,s)\) and only one copy of edges \((v^{in}, v^{out})\) for \(v \in V\) with \(\ell(v^{in}, v^{out}) = 1\), all other (non-specified) values for \(\ell\) and \(u\) are set to default (see 2). Cáceres et al. [7], [8] show that a minimum flow \(f\) in this network corresponds to a MPC of \(G\) (by decomposing \(f\)) and a maximum-sized antichain can be obtained in \(O(|E|)\) time by traversing the residual \(G'_f\) from \(t\): the maximum-sized antichain corresponds to the vertices \(v \in V\) such that \(v^{out}\) is reached by \(t\) in \(G'_f\) but \(v^{in}\) is not. Here, we prove that we obtain the same result when only required to cover \(U \subseteq V\) by setting \(\ell(v^{in}, v^{out}) = 1\) only for \(v \in U\). First, note that a flow in this modified network can be decomposed into a collection of paths covering \(U\) and a collection of paths covering \(U\) corresponds to a feasible flow in this modified network. As such, a minimum flow \(f\) in this modified network can be decomposed into a minimum cardinality set of paths covering \(U\subseteq V\). Moreover, consider the vertices \(V_t\) reached by \(t\) in the residual \(G'_f\) of this modified network. We define \(A \subseteq U\) as \(A = \{v \in U \mid v^{out}\in V_t \land v^{in} \not\in V_t\}\). First note that, if (by contradiction) there is a vertex \(u \in A\) reaching a vertex \(v\in A\) in \(G\), then \(u^{out}\) reaches \(v^{in}\) in \(G'\) and also in \(G'_f\) (edges have default \(\infty\) capacity), a contradiction since \(v^{in}\not\in V_t\). As such, \(A\) is an antichain. Moreover, by definition, \(V_t\) is a \(ts\) cut and all edges entering \(V_t\) have flow equal to their lower bound. Since there is exactly \(|f|\) units of flow entering \(V_t\) (by flow conservation), then \(|A| = |f|\), and thus \(A\) is a maximum-sized antichain \(A \subseteq U\). Computing \(A\) reduces to computing \(V_t\), which can be done in \(O(|E|)\) time. ◻

Proof. We compute a MPC in time \(O(\alpha_1^2|V| + (\alpha_1+k)|E|)\) [7], [8], compute the corresponding minimum flow \(f_1\) in the reduction of 7 and obtain the first greedy antichain \(A_1\) in \(O(|E|)\) time. To obtain the \(i\)-th greedy antichain \(A_i\), for \(i > 1\), we assume that \(U_{i}\) are the vertices still uncovered in iteration \(i\), that is \(U_{i} = V \setminus \bigcup_{j = 1}^{i-1} A_j\), and that \(f_{i-1}\) is a minimum flow as in 7 for \(U_{i-1}\). To compute a minimum flow \(f_i\) for \(U_i\) we use \(f_{i-1}\) as an initial solution. Note that \(f_{i-1}\) is a feasible flow in the network for \(U_{i}\) since \(U_{i} \subseteq U_{i-1}\). Obtaining \(f_i\) from \(f_{i-1}\), can be done by finding \(|f_{i-1}| - |f_{i}|\) decrementing \(ts\) paths in the corresponding residual networks, each in \(O(|E|)\) time. Once we obtain \(f_{i}\), we can obtain \(A_{i}\) (and \(U_{i}\)) in \(O(|E|)\) time by the second part of 7. The total running time after computing the MPC is then \(O\left(|E|\sum_{i = 2}^k |f_{i-1}| - |f_{i}|+1 \right) = O(|E|(k + |f_1| - |f_k|)) = O((\alpha_1+k)|E|)\). ◻

Proof of [thm:approxAlgo]. Combine [lem:approxAlgo1,lem:approxAlgo2]. ◻

Proof. We start by computing an MPC in \(\tilde{O}(\alpha_1|E|)\) time [9], and compute greedy antichains as in the proof of 8 but stopping the computation whenever the next antichain size is at most \(k\) (as we did for chains/paths in the proof of 5) obtaining a collection of greedy antichains: \(\mathcal{A}\). Note that, following the analysis of 8, the running time of computing \(\mathcal{A}\) is \(O((\alpha_1+|\mathcal{A}|)|E|)\). We next prove that \(\mathcal{A}\) is a \(\ln{|V|}\) approximation for the MAS-\(k\) problem. The bound \(|\mathcal{A}| \le \beta_k\ln{|V|}/k\) follows by noting that each antichain in \(\mathcal{A}\) contributes exactly \(k\) units to its \(Sk\)-norm. The fact that \(\mathcal{A}\) is a \(\ln{|V|}\) approximation follows by noting, as in the proof of 5, that the implementation greedy over the set of antichains of \(G\) with weights \(\min(|A|,k)\) for antichain \(A\), is exactly the first antichains of (unweighted) greedy until their size becomes at most \(k\) (for MAS-\(k\)) plus singleton antichains for the yet uncovered vertices (for MAP-\(k\)). The \(Sk\)-norm of the antichain collection (for MAS-\(k\)) is equal to the \(k\)-norm of the antichain partition (for MAP-\(k\)) by [lem:relations]. ◻

Proof. We construct a class of graphs \(G_k\) for \(k \in \mathbb{N}\) and show that greedy covers at most a \(1 - (1-1/k)^k\)-ratio of vertices of \(G_k\), while \(\beta_k = |V|\). We introduce \(k^{k+1}\) vertices that can be covered by \(k\) paths of each \(k^k\) vertices. This set of paths represents the optimal solution and we call the \(i\)-th such path the \(i\)-th row of the graph (see 2). We label the vertices accordingly: \(v_i^j\) with \(i \in [k], \, j\in[k^k]\) denotes the \(j\)-th vertex in the \(i\)-th row. The idea is that greedy will cover a \(1/k\) fraction of the remaining uncovered vertices in each row.

The set of vertices \(C_i \subseteq V(G_k)\) to be covered by the \(i\)-th greedy chain (\(i \in [k]\)) is defined as follows: \(C_i = \{ v_j^\ell \mid j \in [k],\,\ell \in \Gamma_{i,j} \}\), where the index set \(\Gamma_{i,j}\) is defined as the integers inside the following interval: \[\Gamma_{i,j} = \mathbb{N} \cap \begin{cases} [(j-i)(1-\frac{1}{k})^{i-1}k^{k-1}+1,\, (j-i+1)(1-\frac{1}{k})^{i-1}k^{k-1}] &\text{if } j \geq i,\\ [(k+j-i)(1-\frac{1}{k})^{i-1}k^{k-1}+(\sum_{\ell=1}^{j}(1-\frac{1}{k})^{\ell-1})k^{k-1}+1,\\\ \quad(k+j-i+1)(1-\frac{1}{k})^{i-1}k^{k-1}+(\sum_{\ell=1}^{j}(1-\frac{1}{k})^{\ell-1})k^{k-1}] & \text{if } j < i. \end{cases}\]

We add the edges to \(G_k\) that connect consecutive vertices \(v_j^\ell\) in \(C_i\) sorted in ascending order by \(\ell\). Informally, the chains are paths in \(G_k\) that look like stairs, where the \(i\)-th greedy chain starts on the first vertex of row \(i\) and loops from row \(k\) to row \(1\) if \(i > 1\). Clearly, \(G_k\) is a DAG, because all edges have the form \((v_{i_1}^{j_1}, v_{i_2}^{j_2})\) for some \(i_1,i_2 \in [k]\) and \(j_2 > j_1\). We will show the following properties:

1. The sets \(C_i\) are well-defined and pairwise disjoint,

2. The set \(C_i\) is of size \((1-\frac{1}{k})^{i-1}k^k\) and covers \((1-\frac{1}{k})^{i-1}k^{k-1}\) vertices in each row,

3. The \(i\)-th greedy path covers precisely the set \(C_i\) in the worst case.

Showing these three properties concludes the proof, as the number of paths chosen by greedy divided by the optimal solution is the following: \[\frac{1}{\beta_k}\left|\bigcup_{i\in[k]} C_i\right| = \frac{1}{\beta_k}\sum_{i=1}^k |C_i| = \frac{1}{k}\sum_{i=1}^k \left(1-\frac{1}{k}\right)^{i-1} \xrightarrow{k\to\infty} \left(1-\frac{1}{e}\right).\]

Property 1. To verify that the sets \(C_i\) are well-defined, observe that \(\Gamma_{i,j}\subseteq [k^k]\). We now verify that the sets \(C_i\) are pairwise disjoint for \(k \geq 2\). Consider the sets \(C_i\) and \(C_{i-1}\) for some \(i\in\{2,\dots,k\}\) and a row \(j \in [k]\). We show that the intervals in \(\Gamma_{i,j}\) are disjoint by analyzing several cases:

1. If \(j \geq i\), the chain of \(C_i\) is to the left of the chain of \(C_{i-1}\) (that is, the maximum value of \(C_i\) in row \(j\) is smaller than the minimum value of \(C_{i-1}\) in row \(j\)): we have \((j - i + 1)(1-\frac{1}{k})^{i-1}k^{k-1} < (j-i+1)(1-\frac{1}{k})^{i-2}k^{k-1})+1\), since \(0 < (1-\frac{1}{k}) < 1\).

2. If \(j < i - 1\), the chain of \(C_i\) is also to the left of the chain of \(C_{i-1}\): we have \((k+j-i+1)(1-\frac{1}{k})^{i-1}k^{k-1}+(\sum_{\ell=1}^{j}(1-\frac{1}{k})^{\ell-1})k^{k-1} < (k+j-i+1)(1-\frac{1}{k})^{i}k^{k-1}+(\sum_{\ell=1}^{j}(1-\frac{1}{k})^{\ell-1})k^{k-1} + 1\), again, since \(0 < (1-\frac{1}{k}) < 1\).

3. \(C_k\) is to the right of \(C_1\) on all rows \(j\in[k-1]\): We must verify \[\begin{align} j\left(1-\frac{1}{k}\right)^{k-1}k^{k-1}+\left(\sum_{\ell=1}^{j}\left(1-\frac{1}{k}\right)^{\ell-1}\right)k^{k-1} + 1 > jk^{k-1}, \label{eq:ck-right-of-c1} \end{align}\tag{1}\] which is true if and only if \[k^{k-1} \left[ j\left(1-\frac{1}{k}\right)^{k-1} + \sum_{\ell=1}^{j}\left(1-\frac{1}{k}\right)^{\ell-1} - j \right] + 1 > 0.\] Computing the geometric sum, we have \[k^{k-1} \left[ k\left(1-\left(1-\frac{1}{k}\right)^j\right) - j\left(1-\left(1-\frac{1}{k}\right)^{k-1}\right) \right] + 1 > 0.\] It suffices to show that the expression in the bracket is non-negative for all pairs \(k > j \geq 1\). This is implied by \[\begin{align} (k-1)\left(1-\left(1-\frac{1}{k}\right)^{j}\right) &\geq j\left(1-\left(1-\frac{1}{k}\right)^{k-1}\right)\\ \iff \frac{\left(1-\left(1-\frac{1}{k}\right)^{j}\right)}{j} &\geq \frac{\left(1-\left(1-\frac{1}{k}\right)^{k-1}\right)}{k-1}, \end{align}\] which is true, because the function \(f_k(n) = (1-(1-(1/k))^n)(1/n)\) is decreasing. Hence, 1 is true.

The three cases above show that \(C_i\) and \(C_j\) are disjoint for all \(i\neq j \in [k]\).

Property 2. The size of \(C_i\) can be computed by summing the \(k\) interval lengths of \(\Gamma_{i,j}\). Note that by Property 1, the \(C_i\) are pairwise disjoint and that the intervals \(\Gamma_{i,j}\) of a path \(C_i\) all have equal length.

Property 3. To show that greedy takes the path \(C_\ell\), we need to show that \(C_\ell\) covers the most uncovered vertices out of any path after greedy took \(C_1,\dots,C_{\ell-1}\). After covering the first \(\ell-1\) paths and before covering path \(\ell\), we say that greedy is at step \(\ell\). Given a vertex \(v_i^j\), consider the set \(\mathcal{R}_{i,j,\ell}\) of vertices that are in the same row, are uncovered at step \(\ell\) and come after \(v_j^j\): \[\mathcal{R}_{i,j,\ell} = \{ v_i^p \mid p > j,\, v_i^p \text{ uncovered at step \ell} \}.\] We call an edge \((v_{i_1}^{j_1}, v_{i_2}^{j_2})\) forward at step \(\ell\) if \(|\mathcal{R}_{i_1,j_2,\ell}| > |\mathcal{R}_{i_2,j_2,\ell}|\). We show the following Lemma.

Using 9, we now argue that greedy selects the paths \(C_i\) in the worst case. Consider the first greedy step, i.e., before any path was chosen by greedy. Every row has the same length \(k^k\). Using Property 2, the path \(C_1\) also has length \(k^k\), and has the same length \(k^{k-1}\) in every row. By 9, no path is longer than the rows. Thus, in the worst case, greedy chooses \(C_1\). Using induction, we keep this invariant for every path: in the \(i\)-th step, every row has the same number of uncovered vertices, the path \(C_i\) contains the same number of uncovered vertices, and no path contains more uncovered vertices. ◻

Proof. We divide this proof into two parts: first, we give two instances, for \(k=2\) and \(k=3\), of DAGs such that \(k\) greedy antichains cover at most \((3/4)\alpha_k\) vertices. Secondly, we combine these two instances to create an instance for any k. Let \(G_2\) be an instance for \(k=2\) and \(G_3\) be an instance where \(k=3\). See [fig:upperBoundCoverage-II] for \(G_2\) and \(G_3\). In the \(G_i\) instance, for \(i=2,3\), \(\alpha_i = |V(G_i)|\) by selecting \(i\) rows. greedy, however, covers \(8+4 =12\) vertices in \(G_2\) by selecting the blue and red antichains in this order, and covers \(9+6+4=19\) vertices in \(G_3\) by selecting the blue, red, yellow antichains, in this order. This gives us the ratio of \(12/16=3/4\) for \(k=2\) and \(19/27 < 3/4\) for \(k=3\).

To obtain the 3/4 bound for even \(k\), we use \(\frac{k}{2}\) copies of \(G_2\) (called \(G_2^{(1)}, G_2^{(2)}, \dots, G_2^{(\frac{k}{2})}\)). Then we add edges from each vertex in \(G_2^{(i)}\) to each vertex in \(G_2^{(i+1)}\) for all \(i\). These edges make sure that no antichain contains vertices from different \(G_2^{(i)}\). Greedy covers \(3/4\) portion of vertices of each \(G_2\). For odd \(k\), we use \(\frac{k-1}{2}\) copies of \(G_2\) (called \(G_2^{(1)}, G_2^{(2)}, \dots, G_2^{(\frac{k-1}{2})}\)) and one copy of \(G_3\). Then we again add edges from each vertex in \(G_2^{(i)}\) to each vertex in \(G_2^{(i+1)}\) for all \(i\), and also from each vertex in \(G_2^{(\frac{k-1}{2})}\) to each vertex in \(G_3\). Greedy covers at most \(3/4\) portion of vertices of \(G_3\) and each \(G_2\), this gives us the final ratio of \(3/4\). ◻

Proof of [thm:upperBoundCoverage]. Combine [lem:upperBoundCoverage-I,lem:upperBoundCoverage-II]. ◻

Proof. Greedy returns equivalent solutions for MPC and MCP. We show the following:

1. In \(G^C_i\), greedy chooses the alternating path \(P_i\) in its first iteration,

2. \(TC(G^C_i) \setminus P_i = TC(G^C_{i-1})\) for all \(i > 1\).

The second statement implies that after removing the vertices of \(P_i\) from \(TC(G^C_i)\)¹⁰, the set of the remaining edges corresponds to exactly all the paths in \(G^C_{i-1}\). As a result, we can recursively use Statement [stm:greedy95path95chooses95largest95path] and [stm:greedy95path95recurse], to show that the paths \(P_i\) are each taken by greedy.

In the unweighted version of \(G^C_i\), the number of vertices is the sum of all the weights. That is, \(w(V^C_i) = |V^C_i| = \sum_{j = 1}^i |P_j|=\sum_{j = 1}^i 2^{j}-1 < 2^{i+1}\), which implies that the number of greedy paths is \(i \geq \log_2(|V^C_i|)\). Dividing by \(\alpha_1 = 2\), we obtain \(\log_4(|V^C_i|)\) for the factor.

It remains to show both statements. We first show Statement [stm:greedy95path95chooses95largest95path]. Let \(i \geq 2\) and let \(Q = \{ Q[0], \dots, Q[|Q|-1] \}\) be the first path chosen by greedy. We will show that \(P_i\) is the unique largest weight path in \(G^C_i\) and thus, \(Q = P_i\). To observe this, we first note that \(P_i[0]\) is the unique source node of the DAG, which implies that \(Q[0] = P_i[0]\). Assume that \(Q \neq P_i\). We will locally change \(Q\) until \(Q = P_i\) and strictly increase its weight in the process. Let \(j\) be the smallest index of \(Q\) such that \(Q[j] \neq P_i[j]\)

• If \(j = i-1\) (\(P_i[j]\) last vertex of \(P_i\)), since \(P_i\) is the longest alternating path, \(|Q| = i\) and \(Q[j] = P_{i-1}[j-1]\). We reroute \(Q\) to \(P_i[j]\), thus \(w(P_{i-1}[j-1]) = \binom{i-1}{j-1} < \binom{i}{j} = w(P_i[j])\).

• If \(j < i-1\), we reroute \(Q\) by passing it through \(P_i[j]\), and reconnect it again with a later vertex from \(Q\) in the following way:

  • If \(Q\) passes through \(P_i[j+1]\), it did not traverse an alternating edge, and we reroute \(Q\) through \(P_i[j]\) by using the alternating edge to \(P_i[j+1]\). In this case, we replace \[Q = \{ P_i[0], \dots, P_i[j-1], \mathbf{P_{i-1}[j-1], \dots, P_{j}[j-1]}, P_i[j+1], \dots \}\] by \[Q = \{ P_i[0], \dots, P_i[j-1], \mathbf{P_i[j]}, P_i[j+1], \dots \}.\] We have \[w(P_{i-1}[j-1]) + \dots + w(P_{j}[j-1]) = \binom{i-1}{j-1} + \dots + \binom{j}{j-1} < \binom{i}{j} = w(P_i[j]).\]

  • If \(Q\) does not pass through \(P_i[j+1]\), we reroute \(Q\) through \(P_i[j]\) using the unique straight path to reconnect to \(Q\). In this case, we replace \[Q = \{ P_i[0], \dots, P_i[j-1], \mathbf{P_{i-1}[j-1], \dots, P_{i-\ell}[j-1]}, P_{i-\ell}[j], \dots \}\] where \(\ell \leq i-j+1\), by \[Q = \{ P_i[0], \dots, P_i[j-1], \mathbf{P_i[j], P_{i-1}[j], \dots}, P_{i-\ell}[j], \dots \}.\] We have \[w(P_{i-1}[j-1]) + \dots + w(P_{i-\ell}[j-1]) = \binom{i-1}{j-1} + \dots + \binom{i-\ell}{j-1} < \binom{i}{j} = w(P_i[j]).\]

We proceed with growing index \(j\) until we reach the last vertex of \(P_i\). The weight of \(Q\) strictly increased after every reroute, and we thus showed that \(P_i\) is the unique largest weight path in \(G^C_i\). Next, we show Statement [stm:greedy95path95recurse]. Clearly, \(TC(G^C_{i-1}) \subseteq TC(G^C_i) \setminus P_i\). To show the opposite inclusion, let \(u,v \in V^C_{i-1}\), such that the edge \((u,v)\) is in \(TC(G^C_i) \setminus P_i\). Let \(u = P_j[\ell]\) and \(v = P_k[\ell']\), where \(j,k \leq i-1\). We show that there exists a \(uv\)-path in \(G^C_{i-1}\), which shows that the edge \((u,v)\) is also in \(TC(G^C_{i-1})\). Assume that \(u\) and \(v\) are covered by different straight paths (otherwise, the straight path is the \(uv\)-path we are looking for). Then we can consider either \(u' = P_j[\ell+1]\) if \(j > \ell+1\), or \(u' = P_{i-1}[\ell+3]\) if \(j = \ell+1\). In both cases, \(u'\) is the left most vertex on the same straight path as \(v\) satisfying that \((u,u')\) is an edge in \(TC(G^C_{i-1})\). Thus, also \((u', v)\) is an edge in \(TC(G^C_{i-1})\). ◻

Proof. We construct a class of instances \(G^A_i = (V^A_i, E^A_i)\) such that \(|V^A_i| = 2 \cdot 2^i\), \(\beta_1 = 2\) and greedy takes \(i+2\) antichains. This implies the factor of \((i+2) / 2 \geq \log_4(|V^A_i|)\). See 5 for an illustration. The undirected graph underlying the DAG \(G^A_i\) is bipartite, with \(V^A_i = X \cup Y\), \(X = \{ x_1, \dots, x_{2^i} \}\) and \(Y = \{ y_1, \dots, y_{2^i} \}\). Since the graph is bipartite, \(X\) and \(Y\) are both antichains that correspond to the optimal solution. We add edges from \(X\) to \(Y\), such that the following sets become antichains for \(1 \leq k \leq i\): \(T_k = \{ x_j, y_j \mid 2^{k-1} < j \leq 2^k \}\). We let \((x_j, y_{j'}) \in E^A_i\) if and only if they are not both in the same set \(T_k\) (i.e., \(|T_k \cap \{ x_j, y_{j'} \}| \leq 1\) for all \(1 \leq k \leq i\)). Note that if a non-singleton set \(U \subseteq V^A_i\) is an antichain, then it is a subset of some \(T_k\), \(X\) or \(Y\). It can easily be verified by induction that greedy chooses the sets \(T_k\), from \(k=i\) to \(1\), with two singleton vertices \(x_1\) and \(y_1\) left over, that are chosen as two new antichains, hence \(i+2\) antichains in total. ◻

Proof of [thm:lowerBoundPartition]. Combine [lem:lowerBoundPartition-partI,lem:lowerBoundPartition-partII]. ◻

Proof. This proof mimics the proofs of  [18] for the case of paths/antichains of vertices. We first prove the inequality \(\le\), which holds for any \(k\) antichains/\(k\) paths and any path/antichain collection. For the \(\alpha_k\) version, let \(\mathcal{A}\) be \(k\) antichains, \(|\mathcal{A}| = k\), and \(\mathcal{P}\) a collection of paths. Then, note that \[\begin{align} |V(\mathcal{A})| &\le |V\setminus V(\mathcal{P})| + |V(\mathcal{P}) \cap V(\mathcal{A})| \\ &\le |V\setminus V(\mathcal{P})| + \sum_{P\in \mathcal{P}} \sum_{A\in\mathcal{A}}|P \cap A| \\ &\le |V\setminus V(\mathcal{P})| + k|\mathcal{P}| \end{align}\] where the last inequality follows since a path and an antichain can intersect in at most one vertex, i.e., \(|P\cap A| \le 1\). The \(\beta_k\) version of the inequality follows by the same argument (by exchanging the roles of \(\mathcal{P}\) and \(\mathcal{A}\)). To prove that the values meet in the optimum we use the \(\alpha_k\) and \(\beta_k\) networks described in 2. Consider a minimum cost circulation \(f\) in one of the networks. As argued in the main paper, if \(f\) is minimum in the \(\alpha_k\) network, then we can obtain a MPS-\(k\) \(\mathcal{P}_f\) by decomposing \(f\), and if \(f\) is minimum in the \(\beta_k\) network, then we can obtain a MP-\(k\) \(\mathcal{P}_f\) by decomposing \(f\). In both networks, consider the function \(d: V' \rightarrow \mathbb{Z}\) such that \(d(v')\) is the distance of a shortest (minimum cost) path from \(s\) to \(v'\) in the residual \(G'_f\). First, note that since \(f\) is minimum, there are not negative cost cycles in \(G'_f\) and thus \(d\) is well defined. Moreover, \(d(s) = 0\) by definition, and \(d(v') \le 0\) for all \(v'\in V'\) since there is always a path \(P = s, v^{in}, v^{out}, t\) (using \(e_v^2\)) in \(G'_f\) such that all edge costs are \(0\) and \(v' \in P\). Furthermore, since \(d\) is the shortest path distance from \(s\) in \(G'_f\), it follows that for all \(e' = (u', v') \in E'_f\), \(d(v') \le d(u') + c(e')\). In particular, if both an edge \(e' = (u', v')\) and its reverse are in \(E'_f\), then \(d(v') = d(u') + c(e')\). For our networks, this implies:

1. \(d(v') \le d(u')\) if \(e' = (u', v') \in E'\setminus (\{e^1_v \mid v \in V\}\cup \{(t,s)\})\), and \(d(v') = d(u')\) if \(f(e') \ge 1\).

   Cost in such edges is \(c(e') = 0\) and its reverse is in \(E'_f\) if and only if \(f(e') \ge 1\).

2. \(d(v^{out}) \le d(v^{in}) - 1\) if \(f(e^1_v) = 0\), and \(d(v^{out}) \ge d(v^{in}) - 1\) if \(f(e^1_v) = 1\).

   Cost in such edges is \(c(e^1_v) = -1\) and \(e^1_v \in E'_f \Leftrightarrow f(e^1_v) = 0 \Leftrightarrow\) reverse of \(e^1_v \not\in E'_f\).

3. For the \(\alpha_k\) network, \(d(s) = d(t) + k\), since we assume \(f(t, s) \ge 1\): otherwise, there is no path of length more than \(k\) (one such path would reduce \(c(f)\)) and by Mirsky’s theorem [1] a MAP is a MA-\(k\) whose coverage (\(\alpha_k = |V|\)) matches the \(Sk\)-norm of \(\mathcal{P}_f = \emptyset\).

4. For the \(\beta_k\) network, we assume \(f(t,s) = k\): otherwise we can redefine \(f\) to be a different minimum cost circulation with the same cost and \(f(t,s) = k\) (e.g. pick arbitrary \(v\in V\) and push \(k-f(t,s)\) units of flow on \((s, v^{in}), e^2_v, (v^{out}, t)\) and \((t,s)\) at total cost \(0\)).

We define the following subset of vertices \(U_i := \{v' \in V' \mid d(v') \ge i + d(t)\}\) for \(i \in \{1, \ldots, d(s) - d(t)\}\). By definition, \(U'_i\) is an \(st\)-cut (\(s\in U'_i\), \(t\not\in U'_i\)). Moreover, there are no edges, other than \((t,s)\) going into \(U'_i\) in \(G'\): indeed, if \((u', v') \in E'\setminus \{(t,s)\}, u' \not\in U'_i, v'\in U'_i\), then by 1. and 2., \(d(v') \le d(u')\), but also \(d(u') < i + d(t)\) and \(d(v') \ge i + d(t)\) implying \(d(u') < d(v')\), a contradiction. We use \(U_i\) to define subsets of vertices of the input DAG \(G\), \(A_i = \{v\in V\mid v^{in} \in U'_i \land v^{out} \not\in U'_i\}\). In fact, \(A_i\) is an antichain: if \(u\neq v \in A\) are such that there is a \(uv\) path in \(G\), then there is a \(u^{out}v^{in}\) path in \(G'\setminus \{(t,s)\}\), but such a path would cross from \(V'\setminus U_i\) to \(U_i\), a contradiction. We define \(\mathcal{A}_f = \{A_{1}, \ldots, A_{d(s)-d(t)}\}\) to be the collection of antichains extracted from \(f\). Note that in the \(\alpha_k\) network, by 3., \(|\mathcal{A}_f| = k\). And in the \(\beta_k\) network, by 4., \(|\mathcal{P}_f| = k\). These collections satisfy:

a. \(V\setminus V(\mathcal{P}_f) \subseteq V(\mathcal{A}_f)\): indeed, if \(v \in V\setminus V(\mathcal{P}_f)\), then \(f(e^1_v) = 0\) and, by 2., \(d(v^{out}) \le d(v^{in}) - 1\). But then, \(v \in A_{d(v^{in}) - d(t)} \subseteq V(\mathcal{A}_f)\). Note that, \(1 \le d(v^{out}) + 1 - d(t) \le d(v^{in}) - d(t) \le d(s) - d(t)\) since both \((s, v^{in}), (v^{out}, t) \in E'_f\).

b. Thus also \(V\setminus V(\mathcal{A}_f) \subseteq V(\mathcal{P}_f)\).

For the \(\alpha_k\) network we have: \[\begin{align} k|\mathcal{P}_f| &=\\ \text{(by \boldsymbol{3.})} &= (d(s) - d(t))f(t,s)\\ \text{(f is circulation)} &= \sum_{e'=(u',v')\in E'\setminus\{(t,s)\}} (d(u')-d(v'))f(e')\\ &= \sum_{e'=(u',v')\in E'\setminus (\{e^1_v \mid v \in V\}\cup \{(t,s)\})\})} (d(u')-d(v'))f(e') \\ &+ \sum_{e^1_v, v \in V} (d(v^{in})-d(v^{out}))f(e^1_v)\\ \text{(by \boldsymbol{1.})} &= \sum_{e^1_v, v \in V} (d(v^{in})-d(v^{out}))f(e^1_v) \\ \text{(by \boldsymbol{2.})}& = |\{v \in V \mid f(e^1_v) = 1 \land d(v^{in})-d(v^{out}) = 1\}| \\ &\le |V(\mathcal{P}_f) \cap V(\mathcal{A}_f)| \end{align}\]

For the \(\beta_k\) network we have: \[\begin{align} k|\mathcal{A}_f| &=\\ \text{(by \boldsymbol{4.})} &= f(t,s) (d(s) - d(t)) \\ \text{(previous derivation)}&\le |V(\mathcal{P}_f) \cap V(\mathcal{A}_f)| \end{align}\]

For \(\alpha_k\) the proof concludes by: \[\begin{align} |V\setminus V(\mathcal{P}_f)| + k |\mathcal{P}_f| &=\\ \text{(by \boldsymbol{a.})} &= |V(\mathcal{A}_f)\setminus V(\mathcal{P}_f)| + k |\mathcal{P}_f| \\ \text{(derivation for \alpha_k network)} &\le |V(\mathcal{A}_f)\setminus V(\mathcal{P}_f)| + |V(\mathcal{P}_f) \cap V(\mathcal{A}_f)| \\ &= |V(\mathcal{A}_f)| \end{align}\]

Analogously for \(\beta_k\): \[\begin{align} |V\setminus V(\mathcal{A}_f)| + k |\mathcal{A}_f| &=\\ \text{(by \boldsymbol{b.})} &= |V(\mathcal{P}_f)\setminus V(\mathcal{A}_f)| + k |\mathcal{A}_f| \\ \text{(derivation for \beta_k network)} &\le |V(\mathcal{P}_f)\setminus V(\mathcal{A}_f)| + |V(\mathcal{P}_f)\cap V(\mathcal{A}_f)| \\ &= |V(\mathcal{P}_f)| \end{align}\] ◻