p_{i}^{\prime}(Y)=K_{p^{\prime}_{i}}=K_{p_{i+1}},$

where the final equality is by Lemma 4.2(b) and Lemma 4.3(c). Thus, all
inequalities are equations and we have that
$p_{i+1}(Y-\mathcal{Z}_{i})=K_{p_{i+1}}$.

∎

######  Lemma 4.7.

Suppose that the input to Algorithm 1 is a tuple $(p_{1},m_{1})$, where
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a skew-
supermodular function and $m_{1}\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function such that $m_{1}(X)\geq
p_{1}(X)$ for all $X\subseteq V_{1}$ and $m_{1}(u)\leq K_{p_{1}}$ for all
$u\in V_{1}$. Let $\ell\in\Z_{+}$ be the number of recursive calls witnessed
by the execution of Algorithm 1 and, for all $i\in[\ell]$, let $(p_{i},m_{i})$
be the input tuple to the $i^{th}$ recursive call of the execution. Then, for
all $i\in[\ell-1]$, we have the following:

  1. (a)

$\mathcal{Z}_{\leq i}\subseteq\mathcal{Z}_{\leq i+1}$; furthermore,
$\alpha_{i}=\alpha_{i}^{(1)}$ if and only if $\mathcal{Z}_{i}\not=\emptyset$
(i.e., $\mathcal{Z}_{\leq i}\subsetneq\mathcal{Z}_{\leq i+1}$),

  2. (b)

$\calF_{\leq i}\subseteq\calF_{\leq i+1}$; furthermore, if
$\alpha_{i}=\alpha_{i}^{(2)}<\alpha_{i}^{(1)}$, then $\calF_{\leq
i}\subsetneq\calF_{\leq i+1}$,

  3. (c)

$\calD_{i}\subseteq\calD_{i}^{\prime}\subseteq\calD_{i+1}$; furthermore, if
$\alpha_{i}=\alpha_{i}^{(3)}$, then $\calD_{i}\subsetneq\calD_{i}^{\prime}$.

###### Proof.

We recall that by Lemma 4.5, $p_{i}$ is a skew-supermodular function and
$m_{i}$ is a positive function such that $m_{i}(X)\geq p_{i}(X)$ for all
$X\subseteq V_{i}$ and $m_{i}(u)\leq K_{p_{i}}$ for all $u\in V_{i}$. We prove
each property separately below.

  1. (a)

We have that $\calZ_{\leq i}\subseteq\calZ_{\leq i+1}$ by definition. We now
show the second part of the claim. The reverse direction follows because the
function $m$ is a positive function. For the forward direction, suppose that
$\alpha_{i}=\alpha_{i}^{(1)}$. Let $u\in A_{i}$ be a vertex that witnesses
$\alpha_{i}=\alpha_{i}^{(1)}$, i.e. $m_{i}(u)=\alpha_{i}$. Then, we have that
$m_{i}^{\prime}(u)=m_{i}(u)-\alpha_{i}\chi_{A_{i}}(u)=0$. Thus,
$u\in\mathcal{Z}_{i}$.

  2. (b)

We note that $\calF_{\leq i}\subseteq\calF_{\leq i+1}$ follows by definition.
We now show the second part of the claim. Suppose that
$\alpha_{i}=\alpha_{i}^{(2)}<\alpha_{i}^{(1)}$. Then by part (a) of the
current lemma, we have that $\mathcal{Z}_{i}=\emptyset$. Consequently
$p_{i}^{\prime}=p_{i+1}$ by the definition of the two functions. We consider
the family $\calF_{i}^{\prime}$ of minimal $p_{i}^{\prime}$-maximizers. By
Lemma 4.6(a), we have that $\calF_{i}\subseteq\calF_{i}^{\prime}=\calF_{i+1}$,
and thus, $\calF_{\leq i}\subseteq\calF_{\leq
i}\cup\calF_{i}^{\prime}=\calF_{\leq i+1}$, where the equalities in both the
previous expressions are because $p_{i}^{\prime}=p_{i+1}$. We now show that
the first inclusion is strict. For convenience, we let $\calF_{\leq
i}^{\prime}\coloneqq\calF_{\leq i}\cup\calF_{i}^{\prime}$. By way of
contradiction, suppose that $\calF_{\leq i}=\calF_{\leq i}^{\prime}$. Let
$X\subseteq V_{i}-A_{i}$ be a set such that
$\alpha_{i}=\alpha_{i}^{(2)}=K_{p_{i}}-p_{i}(X)$ (such a set exists since
$\alpha_{i}=\alpha_{i}^{(2)}$). Then, we have that
$p_{i}^{\prime}(X)=p_{i}(X)=K_{p_{i}}-\alpha_{i}^{(2)}=K_{p_{i}^{\prime}}.$
Here, the first equality is because $X\subseteq V_{i}-A_{i}$, the second
equality is because our choice of $X$ satisfies
$\alpha_{i}^{(2)}=K_{p_{i}}-p_{i}(X)$, and the final inequality is by Lemma
4.2(b). Thus, the set $X$ is a $p_{i}^{\prime}$-maximizer. Furthermore, $X$ is
not a $p_{i}$-maximizer since $A_{i}$ is a transversal for the family of
$p_{i}$-maximizers by Step 5, but $A_{i}\cap X=\emptyset$. Consequently, there
exists a set $Y\subseteq X$ such that $Y\in\calF_{i}^{\prime}-\calF_{i}$.
Since $\calF_{\leq i}=\calF_{\leq i}^{\prime}$, we have that $Y\in\calF_{\leq
i-1}$. In particular, there exists a recursive call $j\in[i-1]$ such that
$Y\in\calF_{j}$. Since $Y\subseteq V_{i}$, by Lemma 4.6(a), (b) and induction
on $j$, we have that $Y\in\calF_{i}$. Thus, the set $Y$ is a $p_{i}$-maximizer
and so $A_{i}\cap Y\not=\emptyset$ by Step 5, a contradiction to $A_{i}\cap
X=\emptyset$.

  3. (c)

First, we show that $\calD_{i}\subseteq\calD_{i}^{\prime}$. Let
$u\in\calD_{i}$. Then we have the following:

$m_{i}(u)^{\prime}=m_{i}(u)-\alpha_{i}\chi_{A_{i}}(u)=K_{p_{i}}-\alpha_{i}\chi_{A_{i}}(u)=K_{p_{i}}-\alpha_{i}=K_{p_{i}^{\prime}}.$

Here, the second equality is because $u\in\calD_{i}$, the third equality is
because $\calD_{i}\subseteq A_{i}$, and the final equality is by Lemma 4.2(b).
Thus, $u\in\calD_{i}^{\prime}$ and we have that
$\calD_{i}\subseteq\calD_{i}^{\prime}$. Next, we show that
$\calD_{i}^{\prime}\subseteq\calD_{i+1}$. Let $u\in\calD_{i}^{\prime}$. We
note that if $u\in\mathcal{Z}_{i}$, then we have that
$0=m_{i}^{\prime}(u)=K_{p_{i}^{\prime}}$, and thus $i=\ell$, contradicting
$i\in[1,\ell-1]$. Thus, $u\not\in\mathcal{Z}_{i}$, i.e. $u\in V_{i+1}$. Then,
we have that $m_{i+1}(u)=m_{i}^{\prime}(u)=K_{p_{i}^{\prime}}=K_{p_{i+1}}$,
where the final equality is by Lemma 4.2(b) and Lemma 4.3(c). Thus,
$u\in\calD_{i+1}$ and we have that $\calD_{i}^{\prime}\subseteq\calD_{i+1}$.

We now show the second part of the claim. Suppose that
$\alpha_{i}=\alpha_{i}^{(3)}$ and let $v\in V_{i}-A_{i}$ be the vertex which
witnesses $\alpha_{i}=\alpha_{i}^{(3)}$, i.e. $\alpha_{i}=K_{p_{i}}-m_{i}(v)$.
Then, we have that:

$m_{i}^{\prime}(v)=m_{i}(v)-\alpha_{i}\chi_{A_{i}}(v)=m_{i}(v)=K_{p_{i}}-\alpha_{i}=K_{p_{i+1}}.$

Here, the second equality is because $v\in V_{i}-A_{i}$. The third equality is
because the vertex $v$ witnesses $\alpha_{i}=\alpha_{i}^{(3)}$. The final
equality is by Lemma 4.3(c). Thus, $v\in\calD_{i+1}\backslash\calD_{i}$.

∎

The next lemma shows how the function input to an arbitrary recursive call is
related to the function input to the first recursive call. This expression
will be useful in implementing Algorithm 1 since it will allow us to construct
function maximization oracle for $p_{i}$ using only polynomially many queries
to the function maximization oracle of $p_{1}$.

######  Lemma 4.8.

Suppose that the input to Algorithm 1 is a tuple $(p_{1},m_{1})$, where
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a skew-
supermodular function and $m_{1}\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function such that $m_{1}(X)\geq
p_{1}(X)$ for all $X\subseteq V_{1}$ and $m_{1}(u)\leq K_{p_{1}}$ for all
$u\in V_{1}$. Let $\ell\in\Z_{+}$ be the number of recursive calls witnessed
by the execution of Algorithm 1. For $i\in[\ell]$, let $(p_{i},m_{i})$ be the
input tuple to the $i^{th}$ recursive call; moreover, for $i\in[\ell-1]$, let
$\mathcal{Z}_{i},(H^{i}_{0},w^{i}_{0})$ be as defined by Algorithm 1 for the
input $(p_{i},m_{i})$. Then, for each $i\in[\ell]$ we have that

$p_{i}={\left(p_{1}-\sum_{j\in[i-1]}b_{(\tilde{H}_{j},\tilde{w}_{j})}\right)}/_{\bigcup_{j\in[i-1]}\mathcal{Z}_{j}},$

where $(\tilde{H}_{0}^{i},\tilde{w}_{0}^{i})$ denotes the hypergraph obtained
by adding the vertices $\cup_{j\in[i-1]}\mathcal{Z}_{j}$ to the hypergraph
$(H^{i}_{0},w^{i}_{0})$.

###### Proof.

We show the lemma by induction on $i$. The base case $i=1$ trivially holds.
For induction, suppose that $i\geq 2$. Then, we have the following:

$\displaystyle
p_{i}={\left(p_{i-1}-b_{({H}^{i-1}_{0},{w}^{i-1}_{0})}\right)}/_{\mathcal{Z}_{i-1}}$
$\displaystyle={\left({\left(p_{1}-\sum_{j\in[i-2]}b_{(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})}\right)}/_{\bigcup_{j\in[i-2]}\mathcal{Z}_{j}}-b_{({H}^{i-1}_{0},{w}^{i-1}_{0})}\right)}/_{\mathcal{Z}_{i-1}}$
$\displaystyle={\left({\left(p_{1}-\sum_{j\in[i-2]}b_{(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})}\right)}/_{\bigcup_{j\in[i-2]}\mathcal{Z}_{j}}-b_{(\tilde{H}^{i-1}_{0},\tilde{w}^{i-1}_{0})}\right)}/_{\mathcal{Z}_{i-1}}$
$\displaystyle={\left({\left(p_{1}-\sum_{j\in[i-1]}b_{(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})}\right)}/_{\bigcup_{j\in[i-2]}\mathcal{Z}_{j}}\right)}/_{\mathcal{Z}_{i-1}}$

Here, the first equality is by Step 10, the second equality is by the
inductive hypothesis, and the third and fourth equalities are because
$b_{(\tilde{H}_{0}^{i-1},\tilde{w}_{0}^{i-1})}(X)=b_{({H}_{0}^{i-1},{w}_{0}^{i-1})}(X\cap
V_{i-1})$ for all $X\subseteq V$ by definition of the coverage function, where
$V_{i}$ is the ground set at the $i^{th}$ recursive call. Simplifying the
final RHS gives the claimed expression. ∎

We now show the main result of the section which says that an execution of
Algorithm 1 witnesses $O(|V|)$ recursive calls. Since every recursive call
adds at most one new hyperedge to the hypergraph returned by the execution,
this also implies that the number of hyperedges in a solution returned by
Algorithm 1 is $O(|V|)$. This shows property (4) of Theorem 1.7.

######  Lemma 4.9.

Suppose that $V_{1}\not=\emptyset$ and the input to Algorithm 1 is a tuple
$(p_{1},m_{1})$, where $p_{1}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{1}}\rightarrow\Z$ is a skew-supermodular function and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V_{1}\rightarrow\Z_{+}$ is a
positive function such that $m_{1}(X)\geq p_{1}(X)$ for all $X\subseteq V_{1}$
and $m_{1}(u)\leq K_{p_{1}}$ for all $u\in V_{1}$. Let $\ell\in\Z_{+}$ be the
number of recursive calls witnessed by the execution of Algorithm 1. Then,

  1. 1.

the recursion depth $\ell$ of Algorithm 1 is at most $4|V_{1}|-1$, and

  2. 2.

the number of hyperedges in the hypergraph $(H=(V_{1},E),w)$ returned by
Algorithm 1 is at most $4|V_{1}|-1$.

###### Proof.

We note that part (2) of the current lemma follows from part (1) since every
recursive call adds at most one new hyperedge to the hypergraph returned by
the execution in Step 11. Thus, it suffices to show part (1). We define a
potential function $\phi\mathrel{\mathop{\mathchar
58\relax}}[\ell]\rightarrow\Z_{\geq 0}$ as follows: for each $i\in[\ell]$,

$\phi(i)\coloneqq|\mathcal{Z}_{\leq i}|+|\calF_{\leq i}|+|\calD_{i}|.$

By Lemma 4.7, we have that $\phi$ is a monotone increasing function, since
each of the three terms is non-decreasing and at least one of the three terms
strictly increases with increasing $i\in[\ell]$. Consequently, the number of
recursive calls witnessed by the execution of Algorithm 1 is at most
$\phi(\ell)-\phi(0)\leq|\mathcal{Z}_{\leq\ell}|+|\calF_{{\leq\ell}}|+|\calD_{\ell}|\leq
2|V|+|\calF_{{\leq\ell}}|\leq 4|V|-1$. Here, the final inequality is because
the family $\calF_{p_{\leq\ell}}$ is laminar by the following: let
$(p_{i},m_{i})$ denote the input to the $i^{th}$ recursive call of Algorithm
1. By Lemma 4.3(a) and induction on $i$, we have that
$p_{i+1}={(p_{i}-b_{(H_{0}^{i},w_{0}^{i})})}/_{\mathcal{Z}_{i}}$ for every
recursive call $i\in[\ell-1]$. Then, laminarity of the family
$\calF_{p_{\leq\ell}}$ is obtained by applying Lemma 3.2 to the sequence of
functions $p_{1},\ldots,p_{\ell}$. ∎

###  4.4 Runtime

In this section, we show that Algorithm 1 can be implemented to run in
strongly polynomial time provided that the input function $p$ is skew-
supermodular. Lemma 4.11 is the main lemma of this section. Let $i\in[\ell-1]$
be a recursive call of an execution of Algorithm 1. In order to show that the
$i^{th}$ recursive call can be implemented in polynomial time, we will require
the ability to compute a minimal transversal for the family of
$p_{i}$-maximizers in strongly polynomial time (Step 4). We recall that the
function $p_{i}$ is skew-supermodular by Lemma 4.5. Consequently,
$\calF_{p_{i}}$ is a disjoint family by Lemma 3.1. Thus, in order to compute a
transversal for the family $\calF_{p_{i}}$ in strongly polynomial time, it
suffices to explicitly compute the family $\calF_{p_{i}}$ itself in strongly
polynomial time, and pick an arbitrary vertex from each set of the family. We
note that disjointness of the family guarantees that it contains at most a
linear number of sets. The next lemma shows that $\calF_{p_{i}}$ can be
computed in strongly polynomial time using the function maximization oracle
for $p_{i}$.

######  Lemma 4.10.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function. Then, the family $\calF_{p}$ can be computed in
$O(|V|^{3})$ time and $O(|V|^{2})$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. The run-time includes the
time to construct the input to the queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

###### Proof.

We describe a recursive procedure that takes a $p$-maximizer $X\subseteq V$ as
input and returns a minimal $p$-maximizer contained in $X$. For every $u\in
X$, let $Z^{u}$ be the set returned by querying
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=(V-X)\cup\\{u\\},y_{0}\mathrel{\mathop{\mathchar
58\relax}}=\\{0\\}^{V})$. If there exists a vertex $u\in X$ such that the set
$Z^{u}$ is a $p$-maximizer, then recursively compute a minimal $p$-maximizer
contained in $Z^{u}$. Otherwise, return the set $X$.

The correctness of the above procedure is because of the following. The above
procedure terminates (in at most $|V|$ recursive calls) because the
cardinality of the input set $X$ strictly decreases during each recursive call
(i.e., $|X^{\prime}|>|X|$). Let $Y\subseteq X$ be a minimal $p$-maximizer
contained in the set $X$. If $Y=X$, then there are no $p$-maximizers that are
strictly contained in the set $X$. Here, the procedure correctly returns the
set $X$. Alternatively, suppose that $Y\subsetneq X$ and let $u\in X-Y$. Then,
there exists a $p$-maximizer $Z$ such that $Y\subseteq Z\subseteq X-\\{u\\}$.
Consequently, the set $Z^{u}$ computed by the procedure will be a
$p$-maximizer that is strictly contained in the set $X$. Using this fact, the
procedure can be shown to return a minimal $p$-maximizer contained in the set
$X$ by induction on $|X|$.

We now describe a slight modification of the above procedure that leads to an
improved runtime and a smaller number of queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. Let $u\in X$ be a vertex. If
the set $Z^{u}$ is a $p$-maximizer, then we include $u$ in the input set
$T_{0}$ to all ${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ queries in
subsequent recursive calls of the procedure. Alternatively, if the set $Z^{u}$
is not a $p$-maximizer, then we include $u$ in the input set $S_{0}$ to all
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ queries in subsequent
recursive calls procedure. Consequently, the number of queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ (and number of recursive
calls of the procedure) is at most $|V|$. We note that constructing the input
to each query and verifying whether the set returned by the query is a
$p$-maximizer can be done in $O(|V|)$ time. Thus, the procedure terminates in
$O(|V|^{2})$ time. Here, the runtime includes the time to construct the inputs
to the ${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ queries.

We note that by Lemma 3.1, the family $\calF_{p}$ is disjoint. Moreover, one
can compute a set from the family $\calF_{p}$ using the procedure from above.
Thus, the entire family $\calF_{p}$ can be computed by iteratively applying
the procedure from above – each time a set from the family $\calF_{p}$ is
found, it will be included in the input set $T_{0}$ to all
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ queries in subsequent
iterations of the procedure. The lemma follows because each iteration of this
new procedure runs in $O(|V|^{2})$ time and uses at most $|V|$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$; moreover, there are at most
$O(|V|)$ iterations of this new procedure since $|\calF_{p}|=O(|V|)$ by the
disjointness of $\calF_{p}$. ∎

We now show the main lemma of the section which says that Algorithm 1 can be
implemented in strongly polynomial time and polynomial number of calls to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. We remark
that the maximization oracle used in Lemma 4.11 is stronger than the one used
in Lemma 4.10. This stronger version is needed for the input function $p$ in
order to be able to construct the required
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ for all recursive calls
$i\in[\ell]$.

######  Lemma 4.11.

Suppose that the input to Algorithm 1 is a tuple $(p,m)$, where
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a skew-
supermodular function and $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function such that $m(X)\geq p(X)$
for all $X\subseteq V$ and $m(u)\leq K_{p}$ for all $u\in V$. Then, Algorithm
1 can be implemented to run in $O(|V|^{5})$ time using $O(|V|^{4})$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. The run-
time includes the time to construct the hypergraphs used as input to the
queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Moreover,
for each query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, the
hypergraph $(G_{0},c_{0})$ used as input to the query has $|V|$ vertices and
$O(|V|)$ hyperedges.

###### Proof.

We recall that $\ell\in\Z_{+}$ denotes the number of recursive calls witnessed
by the execution of Algorithm 1 and that $(p_{i},m_{i})$ denotes the input
tuple to the $i^{th}$ recursive call of the execution. Let $i\in[\ell]$ be a
recursive call. The next claim shows that all steps of Algorithm 1 except for
Steps 10 and 11 in the $i^{th}$ recursive call can be implemented to run in
strongly polynomial time and strongly polynomial number of queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

######  Claim 4.1.

All steps except for Steps 10 and 11 in the $i^{th}$ recursive call can be
implemented to run in $O(|V_{i}|^{3})$ time using $O(|V_{i}|^{2})$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. The run-time includes
the time to construct the inputs for the queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

###### Proof.

We note that the value $K_{p_{i}}$ can be computed by querying
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,y_{0}\mathrel{\mathop{\mathchar
58\relax}}=\\{0\\}^{V_{i}})$. Step 3 can be computed in $O(|V_{i}|)$ time by
explicitly checking the condition $m_{i}(u)=K_{p_{i}}$ for every $u\in V_{i}$.
By Lemma 4.5 we have that the function $p_{i}$ is skew-supermodular.
Consequently, the family of minimal $p_{i}$-maximizers is a disjoint family by
Lemma 3.1. Moreover, by Lemma 4.10, this family can be computed in
$O(|V_{i}|^{3})$ time using $O(|V_{i}|^{2})$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$, where the runtime
includes the time to construct the inputs for queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. Consequently, by picking
an arbitrary vertex from each set of the family, Steps 4 and 5 can be
implemented in $O(|V_{i}|^{3})$ time using $O(|V_{i}|^{2})$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$, where the runtime
includes the time to construct the inputs for queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. The values
$\alpha_{i}^{(1)}$ and $\alpha_{i}^{(3)}$ can be computed in $O(|V_{i}|)$ time
by iterating over all vertices in $V_{i}$. The value $\alpha_{i}^{(2)}$ can be
computed by the single query
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=A,y_{0}\mathrel{\mathop{\mathchar 58\relax}}=\\{0\\}^{V_{i}})$.
Thus, Step 6 can be implemented in $O(|V_{i}|)$ time using a single query to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$, where the runtime
includes the time to construct the inputs for the query to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. Steps 7 and 9 can be
computed in $O(|V_{i}|)$ time by iterating over all vertices in $V_{i}$. We
note that the number of distinct hyperedges in the hypergraph obtained from
recursion (Step 11) is at most $\ell-i$ since each recursive call adds at most
one distinct hyperedge to the returned. Thus, Steps 12 and 13 can be
implemented in $O(|V_{i}|+\ell)=O(|V_{1}|)$ time, where the equality is
because $\ell=O(|V_{1}|)$ by Lemma 4.9. ∎

Next, we focus on the time to implement a query to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ using
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where
we recall that $p_{1}=p$ is the input function to the initial call to
Algorithm 1.

######  Claim 4.2.

For disjoint subsets $S,T\subseteq V_{i}$ and a vector $y\in\Z^{V_{i}}$, the
answer to the query
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=S,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=T,y_{0}\mathrel{\mathop{\mathchar 58\relax}}=y)$ can be computed in
$O(|V_{1}|^{2})$ time using at most $|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. The
run-time includes the time to construct the inputs for the queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, for each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, the
hypergraph $(G_{0},c_{0})$ used as input to the query has $|V_{1}|$ vertices
and $O(|V_{1}|)$ hyperedges.

###### Proof.

We prove the claim in two steps. In the first step, we will use the expression
for the function $p_{i}$ given by Lemma 4.8 to construct an answer for the
query ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S,T,y)$ using a
single query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$. In
the second step, we will obtain the desired runtime using
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ by
invoking Lemma 2.2.

For every $j\in[i]$, let $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ denote the
hypergraph obtained by adding the vertices $\cup_{k\in[j-1]}\mathcal{Z}_{k}$
to the hypergraph $(H^{k}_{0},w^{k}_{0})$. We now show the first step of the
proof via the following procedure. First, construct the hypergraph $(G,c)$ and
the vector $y_{1}\in\Z^{V_{1}}$, where $G\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j\in[i-1]}\tilde{H}_{0}^{j}$, $c\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j\in[i-1]},\tilde{w}_{0}^{j}$ and
$y_{1}(u)\mathrel{\mathop{\mathchar 58\relax}}=y_{0}(u)$ for every $u\in
V_{i}$, $y_{1}(u)\mathrel{\mathop{\mathchar 58\relax}}=0$ otherwise Next,
obtain $(Z,p_{1}(Z))$ by querying
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,c),S,T,y_{1})$.
Finally, return $(Z-\cup_{j=1}^{i-1}\mathcal{Z}_{j},p(Z))$ as the answer to
the query ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S,T,y)$. We note
that correctness of the procedure is because
$p_{i}={\left(p_{1}-\sum_{j\in[i-1]}b_{(\tilde{H}_{j},\tilde{w}_{j})}\right)}/_{\bigcup_{j\in[i-1]}\mathcal{Z}_{j}}$
by Lemma 4.8.

We now show the second step of the proof. We observe that the hypergraph
$(G,c)$ constructed above has vertex set $V_{1}$ since for every $j\in[i-1]$,
the vertex set of $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ is contained in
$V_{1}$. Moreover, $(G,c)$ has $i-1\leq\ell=O(|V_{1}|)$ hyperedges because for
every $j\in[i-1]$, the hypergraph $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ has
exactly $1$ hyperedge by Step 8, and $\ell=O(|V_{1}|)$ by Lemma 4.9.
Consequently, by Lemma 2.2, the answer to the query
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,c),S,T,y_{1})$
in the above procedure can be computed in $O(|V_{1}|^{2})$ time using
$|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where
the runtime includes the time to construct the inputs to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$;
moreover, the hypergraph used as input to each
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ query
has at most $|V_{1}|$ vertices and $O(|V_{1}|)$ hyperedges. Finally, we note
that the construction of hypergraph $(G,c)$ and returning the (set, value)
pair returned by the above procedure can be implemented in $O(|V_{1}|^{2})$
time and so the claim holds. ∎

We now complete the proof using the two claims above. By 4.1, all steps except
for Steps 10 and 11 in the $i^{th}$ recursive call can be implemented to run
in $O(|V_{i}|^{3})$ time using $O(|V_{i}|^{2})$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. By 4.2, an answer to a
single ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ query can be
computed in $O(|V_{1}|^{2})$ time using at most $|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Thus,
all steps except for Steps 10 and 11 in the $i^{th}$ recursive call can be
implemented to run in $O(|V_{1}|^{4})$ time and $O(|V_{1}|^{3})$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. By
Claims 4.1 and 4.2, the run-time also includes the time to construct the
inputs for the queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, by 4.2, the hypergraph $(G_{0},c_{0})$ used as input to each
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ query
has $|V_{1}|$ vertices and $O(|V_{1}|)$ hyperedges.

We note that Steps 10 and 11 need not be implemented explicitly for the
purposes of the algorithm. Instead,
${p_{i+1}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ can be used to execute
all steps except for Steps 10 and 11 in the $(i+1)^{th}$ recursive call. We
note that 4.2 also enables us to answer a
${p_{i+1}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ query in
$O(|V_{1}|^{2})$ time using at most $|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Thus,
we have shown that each recursive call can be implemented to run in
$O(|V_{1}|^{4})$ time and $O(|V_{1}|^{3})$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is on
an input hypergraph $(G_{0},c_{0})$ that has $|V_{1}|$ vertices and
$O(|V_{1}|)$ hyperedges. By Lemma 4.9, the number of recursive calls witnessed
by the execution of Algorithm 1 is $O(|V_{1}|)$. Thus, Algorithm 1 can be
implemented to run in $O(|V_{1}|^{5})$ time and $O(|V_{1}|^{4})$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where
each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is on
an input hypergraph $(G_{0},c_{0})$ that has $|V_{1}|$ vertices and
$O(|V_{1}|)$ hyperedges. ∎

##  5 Weak Cover using Near-Uniform Hyperedges

In this section, we present an algorithm to obtain a degree-specified near-
uniform weak cover of a function. We emphasize that our algorithm does not
require any assumption on the structure of the input set-function $p$ other
than it being integer-valued and satisfying certain conditions with the input
degree bounds. In subsequent sections where we prove Theorem 1.8 and Theorem
1.9, we will show that this algorithm, when executed on inputs satisfying the
theorem-specific hypotheses (regarding skew-supermodularity of $p$), returns
hypergraphs with the claimed properties of the respective theorems.

In Section 5.1, we present our algorithm (See Algorithm 2). Our algorithm is
recursive in nature. We define the notion of a _feasible execution_ of our
algorithm in the same section. In Section 5.2, we prove that a feasible
execution of the algorithm terminates within finitely many recursive calls.
Here, we also show that it returns a hypergraph satisfying properties (1)–(4)
of Theorem 1.8 and Theorem 1.9. In Section 5.3, we bound the number of
recursive calls of a specific type during feasible executions of our
algorithm—we use this bound in subsequent sections to show properties of our
algorithm when the input function is skew-supermodular or the maximum of two
skew-supermodular functions. In Section 5.4, we turn our attention to the case
where the input is a skew-supermodular function or the maximum of two skew-
supermodular functions. Here, we show that the execution of our algorithm is a
feasible execution on such inputs. In Section 5.5, we bound the run-time of
the algorithm as a function of the recursion depth for skew-supermodular
functions and maximum of two skew-supermodular functions as inputs.

Finally, in Sections 5.6 and 5.7, we use the results from the preceding
sections to prove our main results. In Section 5.6, we bound the number of
recursive calls of type not considered in Section 5.3 for when the input
function $p$ is a skew-supermodular function and complete the proof of Theorem
1.8. In Section 5.7, we bound the number of recursive calls of type not
considered in Section 5.3 for when the input function $p$ is the maximum of
two skew-supermodular functions and complete the proof of Theorem 1.9.

###  5.1 The Algorithm

Our algorithm takes as input (1) a function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$, (2) a positive function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$, and (3) a set
$J\subseteq V$ and returns a hypergraph $\left(H=\left(V,E\right),w\right)$.
We note that in contrast to the non-negative function $m$ appearing in the
statements of Theorem 1.8 and Theorem 1.9, the function $m$ that is input to
our algorithm should be positive. However, the algorithm in this section will
not require the function $p$ to be skew-supermodular. The algorithm is
recursive. The input set $J\subseteq V$ is used to share information between
subsequent recursive calls and is thus a consequence of the recursive nature
of the algorithm. This input parameter can be suppressed if the algorithm is
implemented in an iterative manner.

Our algorithm is LP-based. We define the polyhedron associated with the LP
now. For a set function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ and a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\R_{\geq 0}$, we define the polyhedron $Q(p,m)$ as:

$Q(p,m)\coloneqq\left\\{x\in\R^{V}\ \middle|\begin{array}[]{l}{(\text{i})}{\ \
\ 0\leq x(u)\leq\min\\{1,m(u)\\}}\hfill{\qquad\forall\ u\in V}\\\
{(\text{ii})}{\ \ x(Z)\geq 1}\hfill{\qquad\qquad\qquad\qquad\qquad\forall\
Z\subseteq V\mathrel{\mathop{\mathchar 58\relax}}\ p(Z)=K_{p}}\\\
{(\text{iii})}{\ x(u)=1}\hfill{\qquad\qquad\qquad\qquad\qquad\forall\ u\in
V\mathrel{\mathop{\mathchar 58\relax}}\ m(u)=K_{p}}\\\ {(\text{iv})}{\
x(Z)\leq m(Z)-p(Z)+1}\hfill{\ \ \ \forall\ Z\subseteq V}\\\ {(\text{v})}{\ \
\left\lfloor\frac{m(V)}{K_{p}}\right\rfloor\leq
x(V)\leq\left\lceil\frac{m(V)}{K_{p}}\right\rceil{}\hfill}\\\
\end{array}\right\\}.$ ($Q$-polyhedron)

We now give an informal description of the algorithm (refer to Algorithm 2 for
a formal description). If $V=\emptyset$, then the algorithm returns the empty
hypergraph. Otherwise, the algorithm computes an extreme point optimum
solution $y$ to the LP $\max\\{\sum_{u\in J}y_{u}\mathrel{\mathop{\mathchar
58\relax}}y\in Q(p,m)\\}$ and defines $A$ to be the support of $y$. The
algorithm uses the set $A$ to compute the following five intermediate
quantities $\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)}$:

  * •

$\alpha^{(1)}\coloneqq\min\\{m(u)\mathrel{\mathop{\mathchar 58\relax}}u\in
A\\}$,

  * •

$\alpha^{(2)}\coloneqq\min\left\\{K_{p}-p(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V-A\right\\}$,

  * •

$\alpha^{(3)}\coloneqq\min\left\\{K_{p}-m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in V-A\right\\}$,

  * •

$\alpha^{(4)}\coloneqq\min\left\\{\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor\mathrel{\mathop{\mathchar 58\relax}}|A\cap X|\geq
2\right\\}$, and

  * •

$\alpha^{(5)}\coloneqq\begin{cases}m(V)\mod K_{p}&\text{if
$|A|=\left\lceil{m(V)/K_{p}}\right\rceil>m(V)/K_{p}$,}\\\ K_{p}-(m(V)\mod
K_{p})&\text{if $|A|=\left\lfloor{m(V)/K_{p}}\right\rfloor<m(V)/K_{p}$,}\\\
+\infty&\text{otherwise}\end{cases},$

and defines
$\alpha\coloneqq\min\left\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)}\right\\}$.
Next, the algorithm computes the set $\mathcal{Z}\coloneqq\\{u\in
V\mathrel{\mathop{\mathchar 58\relax}}m(u)-\alpha=0\\}$ and defines
$(H_{0},w_{0})$ to be the hypergraph on vertex set $V$ consisting of a single
hyperedge $A$ with weight $w_{0}(A)=\alpha$. Next, the algorithm defines the
two functions $m^{\prime}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z$
and $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z$ as $m^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=m-\alpha\chi_{A}$, and $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}={m^{\prime}}\backslash_{\mathcal{Z}}$. Next, the algorithm defines
the two functions $p^{\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ and $p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V-\mathcal{Z}}\rightarrow\Z$ as $p^{\prime}\coloneqq
p-b_{(H_{0},w_{0})}$ and
$p^{\prime\prime}\coloneqq{p^{\prime}}/_{\mathcal{Z}}$. The algorithm then
defines the set $J^{\prime\prime}\coloneqq A-\mathcal{Z}$ and recursively
calls itself with the input tuple
$(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$ to obtain a hypergraph
$\left(H^{\prime\prime}=\left(V^{\prime\prime}\coloneqq
V-\mathcal{Z},E^{\prime\prime}\right),w^{\prime\prime}\right)$. Finally, the
algorithm extends the hypergraph $H^{\prime\prime}$ with the set $\mathcal{Z}$
of vertices, adds the set $A$ with weight $\alpha$ as a new hyperedge to the
hyperedge set $E^{\prime\prime}$, and returns the resulting hypergraph. If the
hyperedge $A$ already has non-zero weight in
$(H^{\prime\prime},w^{\prime\prime})$, then the algorithm increases the weight
of the hyperedge $A$ by $\alpha$, and returns the resulting hypergraph.

The definition of the polyhedron $Q(p,m)$ immediately implies the following
lemma.

######  Lemma 5.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set
function with $K_{p}>0$ and $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ be a function. Let $y$ be an integral vector in
$Q(p,m)$ and $A\coloneqq\\{u\in V\mathrel{\mathop{\mathchar
58\relax}}y_{u}>0\\}$. Then, the following properties hold:

  1. (1)

The set $A$ is a transversal for the family of $p$-maximizers,

  2. (2)

$\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}m(u)=K_{p}\\}\subseteq A$,

  3. (3)

$|A\cap Z|\leq m(Z)-p(Z)+1$ for all $Z\subseteq V$, and

  4. (4)

$|A|\in[\lfloor m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$.

We recall that a polyhedron is integral if all its extreme points are
integral. Non-emptiness and integrality of the polyhedron $Q(p,m)$ will be an
important requirement to show properties about Algorithm 2. We will denote
recursive calls of Algorithm 2 during which $Q(p,m)$ is a non-empty integral
polyhedron as _feasible recursive calls_ and say that an execution of
Algorithm 2 is a _feasible execution_ if every recursive call during the
execution is feasible or $V=\emptyset$ in that recursive call. We note that if
$V=\emptyset$ in a recursive call, then the algorithm terminates with that
recursive call.

Algorithm 2 Weak covering with hyperedges

Input: Function $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
positive function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$
Output: Hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$

$\mathbf{\textsc{Algorithm}}\left(p,m,J\right)\mathrel{\mathop{\mathchar
58\relax}}$

1:if $V=\emptyset$ then return Empty Hypergraph
$\left(\left(\emptyset,\emptyset\right),\emptyset\right)$.

2:else:

3: Compute an extreme point optimum solution $y$ to $\max\left\\{\sum_{u\in
J}y_{u}\mathrel{\mathop{\mathchar 58\relax}}y\in Q(p,m)\right\\}$

4: $A\coloneqq\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}y_{u}>0\\}$

5:
$\alpha\coloneqq\min\begin{cases}\alpha^{(1)}\coloneqq\min\left\\{m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in A\right\\}\\\
\alpha^{(2)}\coloneqq\min\left\\{K_{p}-p(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V-A\right\\}\\\
\alpha^{(3)}\coloneqq\min\left\\{K_{p}-m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in V-A\right\\}\\\
\alpha^{(4)}\coloneqq\min\left\\{\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor\mathrel{\mathop{\mathchar 58\relax}}|A\cap X|\geq
2\right\\}\\\ \alpha^{(5)}\coloneqq\begin{cases}m(V)\mod K_{p}&\text{if
$|A|=\left\lceil{m(V)/K_{p}}\right\rceil>m(V)/K_{p}$,}\\\ K_{p}-(m(V)\mod
K_{p})&\text{if $|A|=\left\lfloor{m(V)/K_{p}}\right\rfloor<m(V)/K_{p}$,}\\\
+\infty&\text{otherwise.}\end{cases}\end{cases}$

6: $\mathcal{Z}\coloneqq\left\\{u\in A\mathrel{\mathop{\mathchar
58\relax}}m(u)=\alpha\right\\}$

7: Let
$(H_{0}\coloneqq(V,E_{0}\coloneqq\\{A\\},w_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\\{\alpha\\})$

8: $m^{\prime}\coloneqq m-\alpha\chi_{A}$ and
$m^{\prime\prime}\coloneqq{m^{\prime}}\backslash_{\mathcal{Z}}$

9: $p^{\prime}\coloneqq p-b_{(H_{0},w_{0})}$ and
$p^{\prime\prime}\coloneqq{p^{\prime}}/_{\mathcal{Z}}$

10:
$(H^{\prime\prime},w^{\prime\prime})\coloneqq\textsc{Algorithm}\left(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime}\coloneqq
A-\mathcal{Z}\right)$

11: Obtain $(G,c)$ from $(H^{\prime\prime},w^{\prime\prime})$ by adding
vertices $\mathcal{Z}$

12: return $(G+H_{0},c+w_{0})$

###  5.2 Termination and Partial Correctness of Algorithm 2

This section is devoted to proving that a feasible execution of Algorithm 2
terminates within finite number of recursive calls and returns a hypergraph
satisfying properties (1)–(4) of Theorem 1.8 and Theorem 1.9–see Lemma 5.5. We
also prove certain additional properties in this section about the execution
of Algorithm 2 that will help in subsequent analysis. We emphasize that all
lemmas that appear in this section do not require the function $p$ to be skew-
supermodular. The ideas to prove Lemma 5.5 are modifications of the results
due to Bernáth and Király [8]; we suggest first time readers to skip reading
this section until this lemma and return to them as needed.

We begin with the following lemma which shows that the value $\alpha$ computed
in Step 5 is positive and the function value of the entire ground set for
function $m$ strictly decreases in each feasible recursive call.

######  Lemma 5.2.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$, $m(u)\leq K_{p}$ for all $u\in
V$, and $Q(p,m)$ is a non-empty integral polyhedron. Let $\alpha,\mathcal{Z}$
and $m^{\prime\prime}$ be as defined by Algorithm 2. Then, we have that

  1. (a)

$\alpha\geq 1$, and

  2. (b)

$m^{\prime\prime}(V-\mathcal{Z})<m(V)$.

###### Proof.

We note that since $Q(p,m)$ is non-empty, we have that $V\not=\emptyset$.
Consequently, Algorithm 2 is in its recursive case. We prove both properties
separately below.

  1. (a)

Let $y,A,\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)}$ be
as defined by Algorithm 2. Since $Q(p,m)$ is a non-empty integral polyhedron,
the vector $y$ is the indicator vector of the set $A$. We note that
$\alpha^{(1)}\in\Z_{+}$ since the function $m$ is a positive integer valued
function. Thus, it suffices to show that
$\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)}\in\Z_{+}$.

First, we recall that
$\alpha^{(2)}=\min\\{K_{p}-p(Z)\mathrel{\mathop{\mathchar 58\relax}}Z\subseteq
V-A\\}$. We note that $\alpha^{(2)}\in\Z$ since $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$. Thus, it suffices to show that
$\alpha^{(2)}\geq 1$. By way of contradiction, say $\alpha^{(2)}\leq 0$. Since
$K_{p}\geq p(X)$ for all $X\subseteq V$ by definition, we have that
$\alpha^{(2)}\geq 0$. Thus, $\alpha^{(2)}=0$. Let $X\subseteq V$ be a set that
witnesses $\alpha^{(2)}=0$, i.e. $\alpha^{(2)}=K_{p}-p(X)$ and $X\subseteq
V-A$. Since $\alpha^{(2)}=0$, we have that $p(X)=K_{p}$ and thus, the set $X$
is a $p$-maximizer that is disjoint from the set $A$. This contradicts Lemma
5.1(1).

Next, we recall that $\alpha^{(3)}=\min\\{K_{p}-m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in V-A\\}$. We note that $\alpha^{(3)}\in\Z$ since $K_{p}\in\Z$
and $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z$. Thus, it suffices
to show that $\alpha^{(3)}\geq 1$. By way of contradiction, say
$\alpha^{(3)}\leq 0$. Since $K_{p}\geq m(u)$ for all $u\in V$, we have that
$\alpha^{(3)}\geq 0$. Thus, $\alpha^{(3)}=0$. Let $v\in V$ be a vertex that
witnesses $\alpha^{(3)}=0$, i.e. $\alpha^{(3)}=K_{p}-m(v)$ and $v\in V-A$.
Since $\alpha^{(3)}=0$, we have that $m(v)=K_{p}$. However, this contradicts
Lemma 5.1(2).

Next, we recall that
$\alpha^{(4)}=\min\left\\{\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor\mathrel{\mathop{\mathchar 58\relax}}|A\cap X|\geq
2\right\\}$. We note that $\alpha^{(4)}\in\Z$ by definition and so it suffices
to show that $\alpha^{(4)}\geq 1$. By way of contradiction, say
$\alpha^{(4)}\leq 0$. Since $m(X)\geq p(X)$ for every $X\subseteq V$, we have
that $\alpha^{(4)}\geq 0$. Thus, $\alpha^{(4)}=0$. Let $Z\subseteq V$ be a set
that witnesses $\alpha^{(4)}=0$, i.e.
$Z\coloneqq\arg\min\left\\{\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor\mathrel{\mathop{\mathchar 58\relax}}|A\cap X|\geq
2\right\\}$. Consequently, we have that $\frac{m(Z)-p(Z)}{|A\cap Z|-1}<1$.
However, this gives us that $m(Z)-|A\cap Z|<p(Z)-1$, contradicting Lemma
5.1(3).

Finally, we recall that

$\alpha^{(5)}\coloneqq\begin{cases}m(V)\mod K_{p}&\text{if
$|A|=\left\lceil{m(V)/K_{p}}\right\rceil>m(V)/K_{p}$,}\\\ K_{p}-(m(V)\mod
K_{p})&\text{if $|A|=\left\lfloor{m(V)/K_{p}}\right\rfloor<m(V)/K_{p}$,}\\\
+\infty&\text{otherwise.}\end{cases}$

If $\alpha^{(5)}=\infty$, then we are done. Suppose that
$\alpha^{(5)}\neq\infty$. Then, $m(V)/K_{p}$ is not an integer. By definition,
this immediately implies that $\alpha^{(5)}\geq 1$.

  2. (b)

Let $A,m^{\prime}$ be as defined by Algorithm 2. Since $Q(p,m)$ is non-empty,
we have that $A\neq\emptyset$. By part (1) of the current lemma, we have that
$\alpha\geq 1$. Hence, $m^{\prime}(V)=m(V)-\alpha\chi_{A}<m(V)$ by Step 8.
Since the function $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}{V-\mathcal{Z}}\rightarrow\Z$ is defined as
$m^{\prime\prime}={(m-\alpha\chi_{A})}\backslash_{\mathcal{Z}}$ by Step 9, we
have that $m^{\prime\prime}(V-\mathcal{Z})=m^{\prime}(V)<m(V)$ and the claim
holds.

∎

The next two lemmas will allow us to conclude that if the input functions $p$
and $m$ to a feasible recursive call of Algorithm 2 satisfy certain
conditions, then the intermediate functions $p^{\prime},m^{\prime}$ and the
input functions to the subsequent recursive call
$p^{\prime\prime},m^{\prime\prime}$ also satisfy the same conditions. Such
recursive properties will be useful in inductively proving properties about
Algorithm 2.

######  Lemma 5.3.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$, $m(u)\leq K_{p}$ for all $u\in
V$, and $Q(p,m)$ is a non-empty integral polyhedron. Let $p^{\prime}$,
$m^{\prime}$ and $\alpha$ be as defined by Algorithm 2. Then, the following
hold:

  1. (a)

The function $m^{\prime}\mathrel{\mathop{\mathchar
58\relax}}V^{\prime}\rightarrow\Z_{\geq 0}$ is a non-negative function,

  2. (b)

$K_{p^{\prime}}\coloneqq K_{p}-\alpha$,

  3. (c)

$m^{\prime}(u)\leq K_{p^{\prime}}$ for all $u\in V^{\prime}$, and

  4. (d)

$m^{\prime}(X)\geq p^{\prime}(X)$ for all $X\subseteq V^{\prime}$.

###### Proof.

We note that since $Q(p,m)$ is non-empty, we have that $V\not=\emptyset$.
Consequently, Algorithm 2 is in its recursive case. Moreover, since since
$Q(p,m)$ is an integral polyhedron, the vector $y$ is the indicator vector of
the set $A$, where $y$ and $A$ are as defined by the algorithm. Let
$\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)},\alpha$, and
$(H_{0}=(V,E_{0}\coloneqq\\{A\\},w_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\\{\alpha\\})$ be as defined by the algorithm. We
show that the functions $m^{\prime}$ and $p^{\prime}$ satisfy each of the
properties (a)-(d) below.

  1. (a)

The function $m^{\prime}$ is non-negative due to the following: if the vertex
$u\not\in A$, then $m^{\prime}(u)=m(u)\geq 0$. Otherwise $u\in A$ and we have
that $m^{\prime}(u)=m(u)-\alpha\geq m(u)-\alpha^{(1)}\geq 0$, where the last
inequality is by definition of $\alpha^{(1)}$ in Step 5.

  2. (b)

Let $X\subseteq V$ be a $p$-maximizer and $Y\subseteq V$ be a
$p^{\prime}$-maximizer. We recall that the set $A$ is a transversal for the
family of $p$-maximizers by Lemma 5.1(1), and consequently, $|A\cap X|\geq 1$.
Thus, $K_{p^{\prime}}=p^{\prime}(Y)\geq
p^{\prime}(X)=p(X)-\alpha=K_{p}-\alpha$, where the inequality is because the
set $Y$ is a $p^{\prime}$-maximizer, and the second equality is because
$|A\cap X|\geq 1$ and the definition of the function $p^{\prime}$ in Step 9.
We now show that $K_{p^{\prime}}\leq K_{p}-\alpha$. If the set $Y$ is also a
$p$-maximizer, then the claim holds since we have that
$K_{p^{\prime}}=p^{\prime}(Y)=p(Y)-\alpha=K_{p}-\alpha$, where the second
equality is because the set $A$ is a transversal for the family of
$p$-maximizers. Thus, we may assume that $Y$ is not a $p$-maximizer. If
$|A\cap Y|\geq 1$, then we have that

$p(X)-\alpha\leq p^{\prime}(Y)=p(Y)-\alpha\leq p(X)-\alpha,$

where the first inequality is because we have already shown that
$K_{p^{\prime}}\geq K_{p}-\alpha$, the equality is because of $|A\cap Y|\geq
1$ and the definition of $p^{\prime}$ in Step 9, and the final inequality is
because the set $X$ is a $p$-maximizer. Thus, all inequalities are equations
and the claim holds. Otherwise, suppose that $|A\cap Y|=0$. Here, we have that

$p(X)-\alpha\geq p(X)-\alpha^{(2)}\geq
p(X)-\left(p(X)-p(Y)\right)=p(Y)=p^{\prime}(Y),$

where the first inequality is because $\alpha\leq\alpha^{(2)}$ in Step 5, the
second inequality is by definition of $\alpha^{(2)}$ in Step 5 and the fact
that the set $X$ is a $p$-maximizer, and the final equality is because of
$|A\cap Y|=0$ and definition of the function $p^{\prime}$ in Step 9.

  3. (c)

Suppose $u\in A$. Then, we have that $m^{\prime}(u)=m(u)-\alpha\leq
K_{p}-\alpha=K_{p^{\prime}}$, where the first equality is by definition of
$m^{\prime}$ in Step 8 and the final equality is by part (b) of the current
lemma. Next, suppose $u\in V-A$, implying $m^{\prime}(u)=m(u)$. In particular,
we have that $K_{p}-m^{\prime}(u)=K_{p}-m(u)\geq\alpha^{(3)}\geq\alpha$, where
the first inequality is by definition of $\alpha^{(3)}$ and the second
inequality is by definition of $\alpha$ in Step 5. Rearranging the terms, we
get that $K_{p^{\prime}}=K_{p}-\alpha\geq m^{\prime}(u)$, where the first
equality is again by part (b) of the current lemma.

  4. (d)

Let $X\subseteq V$ be arbitrary. Suppose that $|X\cap A|=0$. Then,
$b_{(H_{0},w_{0})}(X)=0$ and hence $m^{\prime}(X)=m(X)\geq
p(X)=p^{\prime}(X)$, so the claim holds. Suppose that $|X\cap A|\geq 1$. Then,
we have the following:

$m^{\prime}(X)=m(X)-\alpha|X\cap A|\geq
p(X)-\alpha=p(X)-b_{(H_{0},w_{0})}(X)=p^{\prime}(X).$

Here, the inequality holds trivially if $|X\cap A|=1$, while for $|X\cap
A|\geq 2$ it holds because $\alpha\geq\alpha^{(4)}$ in Step 5. The last
equality is because $|X\cap A|\geq 1$.

∎

######  Lemma 5.4.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$, $m(u)\leq K_{p}$ for all $u\in
V$, and $Q(p,m)$ is a non-empty integral polyhedron. Let
$\alpha,\alpha^{(5)},\mathcal{Z},p^{\prime\prime}$ and $m^{\prime\prime}$ be
as defined by Algorithm 2. Then, the following hold:

  1. (a)

The function $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z_{+}$ is a positive function,

  2. (b)

$K_{p^{\prime\prime}}=K_{p}-\alpha$,

  3. (c)

$m^{\prime\prime}(u)\leq K_{p^{\prime\prime}}$ for all $u\in
V^{\prime\prime}$,

  4. (d)

$m^{\prime\prime}(X)\geq p^{\prime\prime}(X)$ for all $X\subseteq
V^{\prime\prime}$, and

  5. (e)

either $K_{p^{\prime\prime}}=0$ or
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\in[\lfloor
m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$; furthermore, if
$K_{p^{\prime\prime}}>0$ and $\alpha<\alpha^{(5)}$, then we have that

$\left\lfloor{(m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}}\right\rfloor=\left\lfloor{(m(V)/K_{p}}\right\rfloor\text{
and
}\left\lceil{(m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}}\right\rceil=\left\lceil{m(V)/K_{p}}\right\rceil.$

###### Proof.

We note that since $Q(p,m)$ is non-empty, we have that $V\not=\emptyset$.
Consequently, Algorithm 2 is in its recursive case. Let $A$,
$p^{\prime}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, and
$m^{\prime}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z$ be as defined
by the Algorithm 2. We show that the functions $m^{\prime\prime}$ and
$p^{\prime\prime}$ satisfy each of the properties (a)-(d) below.

  1. (a)

We have that $m^{\prime\prime}(u)=m^{\prime}(u)>0$ for every $u\in
V-\mathcal{Z}$, where the inequality is by Lemma 5.3(a) and the definition of
the set $\mathcal{Z}$ in Step 6.

  2. (b)

By Lemma 5.3(b), it suffices to show that
$K_{p^{\prime\prime}}=K_{p^{\prime}}$. Let $X\uplus R_{X}$ be a
$p^{\prime}$-maximizer, where $R_{X}\subseteq\mathcal{Z}$ and $X\subseteq
V-\mathcal{Z}$. Furthermore, let $Y\subseteq V-\mathcal{Z}$ be a
$p^{\prime\prime}$-maximizer such that $p^{\prime\prime}(Y)=p^{\prime}(Y\uplus
R_{Y})$ where $R_{Y}\subseteq\mathcal{Z}$. Then, we have the following:

$K_{p^{\prime}}=p^{\prime}(X\uplus R_{X})\leq\max\left\\{p^{\prime}(X\uplus
R^{\prime})\mathrel{\mathop{\mathchar
58\relax}}R^{\prime}\subseteq\mathcal{Z}\right\\}=p^{\prime\prime}(X)\leq
K_{p^{\prime\prime}}=p^{\prime\prime}(Y)=p^{\prime}(Y\uplus R_{Y})\leq
K_{p^{\prime}}.$

Thus, all inequalities are equations.

  3. (c)

Let $u\in V-\mathcal{Z}$. Then we have that
$m^{\prime\prime}(u)=m^{\prime}(u)\leq K_{p^{\prime}}=K_{p^{\prime\prime}}$,
where the inequality is by Lemma 5.3(c) and the final equality is by Lemma
5.3(b) and part (b) of the current lemma.

  4. (d)

Let $X\subseteq V-\mathcal{Z}$ be arbitrary. Let $R\subseteq\mathcal{Z}$ such
that $p^{\prime\prime}(X)=p^{\prime}(X\uplus R)$. Then, we have that
$m^{\prime\prime}(X)=m^{\prime}(X\uplus R)\geq p^{\prime}(X\uplus
R)=p^{\prime\prime}(X)$. Here, the first equality is because
$R\subseteq\mathcal{Z}$ and the inequality is by Lemma 5.3(d).

  5. (e)

We note that $K_{p^{\prime\prime}}\geq 0$ because
$K_{p^{\prime\prime}}=K_{p}-\alpha\geq K_{p}-\alpha^{(1)}\geq K_{p}-m(u)\geq
0$ for every $u\in A$, where the final inequality is because $m(u)\leq K_{p}$
for every $u\in V$. Suppose that $K_{p^{\prime\prime}}>0$. By Lemma 5.1(4), we
know that $|A|\in[\lfloor m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$. First,
we consider the case where $m(V)/K_{p}\in\Z$. Then, we have that
$|A|=m(V)/K_{p}$ and hence,

$\frac{m^{\prime\prime}(V-\mathcal{Z})}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha|A|}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha\frac{m(V)}{K_{p}}}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha\frac{m(V)}{K_{p}}}{K_{p}-\alpha}=\frac{m(V)}{K_{p}},$

where the third equality is by Lemma 5.3(b). Here, we also observe that the
second part of the claim holds (regardless of the value of $\alpha$). Next,
suppose that $m(V)/K_{p}\not\in\Z$. Let $d,r\in\Z_{+}$ be positive integers
such that $m(V)=d\cdot K_{p}+r$ with $r<K_{p}$ (such a $d$ and $r$ exist since
$m$ is a positive function, $m(Z)\geq p(Z)$ for every $Z\subseteq V$, and
$m(V)/K_{p}\not\in\Z$). We note that $d=\lfloor m(V)/K_{p}\rfloor$ and
$d+1=\lceil m(V)/K_{p}\rceil$ and hence, it suffices to show that
$m^{\prime\prime}(V-\mathcal{Z})/K_{p}\in[d,d+1]$. We consider two cases. For
he first case, suppose that $|A|=\lfloor m(V)/K_{p}\rfloor$. This implies that
$|A|=d$ and $\alpha\leq\alpha^{(5)}=K_{p}-r$. Then, we have the following:

$\frac{m^{\prime\prime}(V-\mathcal{Z})}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha|A|}{K_{p}-\alpha}=\frac{dK_{p}+r-\alpha
d}{K_{p}-\alpha}\in[d,d+1].$

For the second case, suppose that $|A|=\lceil m(V)/K_{p}\rceil$. This implies
that $|A|=d+1$ and $\alpha\leq\alpha^{(5)}=r$. Then, we have the following:

$\frac{m^{\prime\prime}(V-\mathcal{Z})}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha|A|}{K_{p}-\alpha}=\frac{dK_{p}+r-\alpha(d+1)}{K_{p}-\alpha}\in[d,d+1].$

Then, the first part of the claim holds by the final inclusions in both cases
above. Furthermore, we observe that in both cases, the final inclusions are in
the range $(d,d+1)$ if $\alpha<\alpha^{(5)}$. Consequently,
$\left\lfloor{m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}}\right\rfloor=d$
and
$\left\lceil{m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}}\right\rceil=d+1$
and so the second part of the claim also holds.

∎

We recall that an execution of Algorithm 2 is feasible if the $Q(p,m)$
polyhedron is integral for every recursive call of the algorithm. We now show
the main lemma of the section which says that a feasible execution of
Algorithm 2 terminates within a finite number of recursive calls and returns a
hypergraph satisfying properties (1)–(4) of Theorem 1.8 and Theorem 1.9.

######  Lemma 5.5.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$ and $m(u)\leq K_{p}$ for all $u\in
V$, and the execution of Algorithm 2 for the input tuple $(p,m,J)$ is
feasible. Then, Algorithm 2 terminates in a finite (weakly-polynomial) number
of recursive calls. Furthermore, the hypergraph
$\left(H=\left(V,E\right),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ returned by Algorithm 2 satisfies the
following properties:

  1. (1)

$b_{(H,w)}(X)\geq p(X)$ for all $X\subseteq V$,

  2. (2)

$b_{(H,w)}(u)=m(u)$ for all $u\in V$,

  3. (3)

$\sum_{e\in E}w(e)=K_{p}$, and

  4. (4)

if $K_{p}>0$, then $|e|\in[\lfloor m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$
for all $e\in E$.

###### Proof.

We prove the lemma by induction on the potential function $\phi(m)\coloneqq
m(V)$. We note that $\phi(m)\geq 0$ since $m$ is a positive function. For the
base case of induction, suppose that $\phi(m)=0$. Then, we have that
$V=\emptyset$ since $m$ is a positive function. Consequently, Algorithm 2 is
in its base case (Step 1) and terminates. Moreover, Step 1 returns an empty
hypergraph which satisfies properties (1)-(4) and so the lemma holds. Here, we
note that $K_{p}\leq 0$ since otherwise, we have that $0=m(\emptyset)\geq
p(\emptyset)>0$, a contradiction.

For the inductive case, suppose that $\phi(m)>0$. We note that since $m$ is a
positive function, we have that $V\not=\emptyset$ and $K_{p}\geq m(u)>0$ for
every $u\in V$. Consequently, Algorithm 2 is in its recursive case. Since the
execution of Algorithm 2 is feasible for the input tuple $(p,m,J)$, we have
that $Q(p,m)$ is a non-empty integral polyhedron. By Lemma 5.4(a), (c) and
(d), the tuple $(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$
constructed by Algorithm 2 satisfy the hypothesis of the current lemma. We
note that the tuple $(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$ is
the input to the subsequent recursive call of Algorithm 2 by Step 10.
Moreover, $\phi(m^{\prime\prime})<\phi(m)$ by Lemma 5.2(b). Thus, by
induction, the subsequent recursive call to Algorithm 2 terminates and returns
a hypergraph
$(H^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime}),w^{\prime\prime})$
satisfying properties (1)-(4) for the tuple
$(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$. Consequently, the
entire execution of Algorithm 2 terminates within a finite number of recursive
calls. Let $(H=(V,E),w)$ be the hypergraph returned by Step 10 and let
$(H_{0},w_{0}),\mathcal{Z},A,\alpha$ be as defined by Algorithm 2 for the
input tuple $(p,m,J)$. We first show that the hypergraph $(H,w)$ satisfies
property (1). Let $X\subseteq V$ be arbitrary. Then, we have that

$\displaystyle b_{(H,w)}(X)$
$\displaystyle=b_{(H^{\prime\prime},w^{\prime\prime})}(X-\mathcal{Z})+b_{(H_{0},w_{0})}(X)$
$\displaystyle\geq p^{\prime\prime}(X-\mathcal{Z})+b_{(H_{0},w_{0})}(X)$
$\displaystyle\geq p^{\prime}(X)+b_{(H_{0},w_{0})}(X)$ $\displaystyle=p(X).$

Here, the first inequality holds by the inductive hypothesis property (1) and
the second inequality is because
$p^{\prime\prime}={p^{\prime}}/_{\mathcal{Z}}$ by Step 9. Next, we show that
hypergraph $(H,w)$ satisfies property (2). Let $u\in V$ be arbitrary. Then, we
have the following:

$\displaystyle b_{(H,w)}(u)$
$\displaystyle=b_{(H^{\prime\prime},w^{\prime\prime})}(u)+b_{(H_{0},w_{0})}(u)$
$\displaystyle=b_{(H^{\prime\prime},w^{\prime\prime})}(u)+\alpha\chi_{A}(u)$
$\displaystyle=m^{\prime\prime}(u)+\alpha\chi_{A}(u)$ $\displaystyle=m(u).$

Here, the third equality is by the inductive hypothesis property (2). Next, we
show that the hypergraph $(H,w)$ satisfies property (3). We have the
following:

$\sum_{e\in E}w(e)=\sum_{e\in E^{\prime\prime}}w(e)+w(A)=\sum_{e\in
E^{\prime\prime}}w^{\prime\prime}(e)+\alpha=K_{p^{\prime\prime}}+\alpha=K_{p}.$

Here, the third equality is by induction hypothesis property (3), and the
final equality is by Lemma 5.4(b). Next, we show that property (4) holds. Let
$e\in E$ be an arbitrary hyperedge. We consider two cases. First, suppose that
$e\in E-E^{\prime\prime}$. Then, we have that $e=A$ by Steps 7, 11 and 12.
Consequently, we have that $|e|=|A|\in[\lfloor m(V)/K_{p}\rfloor,\lceil
m(V)/K_{p}\rceil]$ by Lemma 5.1(4). Alternatively, suppose that $e\in
E^{\prime\prime}$. We note that $|E^{\prime\prime}|>0$ implies that
$K_{p^{\prime\prime}}>0$ by property (3) of the inductive hypothesis.
Moreover, $|e|\in[\lfloor
m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}\rfloor,\lceil
m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}\rceil]$ by the
induction hypothesis property (4). By Lemma 5.4(e), we have that
$m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}\in[\lfloor
m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$. Thus, the interval $[\lfloor
m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}\rfloor,\lceil
m^{\prime\prime}(V^{\prime\prime})/K_{p^{\prime\prime}}\rceil]$ is contained
in the interval $[\lfloor m(V)/K_{p}\rfloor,\lceil m(V)/K_{p}\rceil]$ and so
property (4) holds. ∎

We conclude the section by showing two properties of Algorithm 2 which we will
leverage in subsequent sections while analyzing the recursion depth and
runtime of the algorithm. The first lemma below shows that any feasible
execution of Algorithm 2 can witness $\alpha=\alpha^{(5)}$ in at most one
recursive call. The second lemma below shows that the set $A$ chosen during a
feasible recursive call of Algorithm 2 is not feasible for the subsequent
recursive call. As a consequence, the value $\alpha$ computed in Step 5 during
a feasible recursive call of Algorithm 2 is the maximum value such that the
input tuple $(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$ to the
subsequent recursive call in Step 10 satisfy the hypothesis of Lemma 5.5.

######  Lemma 5.6.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$, $m(u)\leq K_{p}$ for all $u\in
V$, and $Q(p,m)$ is a non-empty integral polyhedron. Let
$A,\alpha^{(5)},\alpha,\mathcal{Z},p^{\prime\prime},m^{\prime\prime}$ be as
defined by Algorithm 2. If $\alpha=\alpha^{(5)}$ and $K_{p^{\prime\prime}}>0$,
then $m(V)/K_{p}\not\in\Z$,
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\in\Z$, and
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\neq|A|$.

###### Proof.

We note that since $Q(p,m)$ is non-empty, we have that $V\not=\emptyset$ and
consequently Algorithm 2 is in its recursive case. Since
$\alpha=\alpha^{(5)}$, it follows that $\alpha^{(5)}<\infty$ (because
$\alpha^{(5)}=\alpha\leq\alpha^{(1)}\leq\max_{u\in V}m(u)<\infty$, where final
inequality is because the range of $m$ is $\Z_{+}$). and hence,
$m(V)/K_{p}\not\in\Z$ by definition of $\alpha^{(5)}$ in Step 5. Next, we
prove the conclusions about
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}$. Let $d,r\in\Z_{+}$ be
positive integers such that $m(V)=d\cdot K_{p}+r$ with $r<K_{p}$ (such a $d$
and $r$ exist since $m$ is a positive function, $m(Z)\geq p(Z)$ for every
$Z\subseteq V$, and $m(V)/K_{p}\not\in\Z$). We note that $d=\lfloor
m(V)/K_{p}\rfloor$ and $d+1=\lceil m(V)/K_{p}\rceil$. We consider two cases:
Firstly, suppose that $|A|=\lfloor m(V)/K_{p}\rfloor$. It implies that $|A|=d$
and $\alpha=\alpha^{(5)}=K_{p}-r$. Then, we have the following:

$\frac{m^{\prime\prime}(V-\mathcal{Z})}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha|A|}{K_{p}-\alpha}=\frac{dK_{p}+r-(K_{p}-r)d}{K_{p}-K_{p}-r}=d+1,$

and hence, $m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\in\Z$ and
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\neq|A|$. In the above,
the first equality is by definition of $m^{\prime\prime}$ in Step 8 and by
Lemma 5.4(b). Next, suppose that $|A|=\lceil m(V)/K_{p}\rceil$. It implies
that $|A|=d+1$ and $\alpha=\alpha^{(5)}=r$. Then, we have the following:

$\frac{m^{\prime\prime}(V-\mathcal{Z})}{K_{p^{\prime\prime}}}=\frac{m(V)-\alpha|A|}{K_{p}-\alpha}=\frac{dK_{p}+r-r(d+1)}{K_{p}-r}=d,$

and hence, $m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\in\Z$ and
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\neq|A|$. In the above,
the first equality is by definition of $m^{\prime\prime}$ in Step 8 and by
Lemma 5.4(b).

∎

######  Lemma 5.7.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a set function, and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a function such
that $m(X)\geq p(X)$ for all $X\subseteq V$, $m(u)\leq K_{p}$ for all $u\in
V$, and $Q(p,m)$ is a non-empty integral polyhedron. Let
$A,\mathcal{Z},p^{\prime\prime},m^{\prime\prime}$ be as defined by Algorithm
2. If $A\cap\mathcal{Z}=\emptyset$ and $K_{p^{\prime\prime}}>0$, then the
indicator vector $\chi_{A}\in\\{0,1\\}^{V-\mathcal{Z}}$ is not in
$Q(p^{\prime\prime},m^{\prime\prime})$.

###### Proof.

We note that since $Q(p,m)$ is non-empty, we have that $V\not=\emptyset$ and
consequently Algorithm 2 is in its recursive case. By way of contradiction,
suppose that $A\cap\mathcal{Z}=\emptyset$ and the indicator vector
$\chi_{A}\in\\{0,1\\}^{V-\mathcal{Z}}$ is in
$Q(p^{\prime\prime},m^{\prime\prime})$. Consequently, the set $A$ satisfies
the properties Lemma 5.1(1)-(4) with respect to the functions
$p^{\prime\prime}$ and $m^{\prime\prime}$. We recall the definition of
$\alpha$ below:

$\alpha\coloneqq\min\begin{cases}\alpha^{(1)}\coloneqq\min\left\\{m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in A\right\\}\\\
\alpha^{(2)}\coloneqq\min\left\\{K_{p}-p(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V-A\right\\}\\\
\alpha^{(3)}\coloneqq\min\left\\{K_{p}-m(u)\mathrel{\mathop{\mathchar
58\relax}}u\in V-A\right\\}\\\
\alpha^{(4)}\coloneqq\min\left\\{\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor\mathrel{\mathop{\mathchar 58\relax}}|A\cap X|\geq
2\right\\}\\\ \alpha^{(5)}\coloneqq\begin{cases}m(V)\mod K_{p}&\text{if
$|A|=\left\lceil{m(V)/K_{p}}\right\rceil>m(V)/K_{p}$,}\\\ K_{p}-(m(V)\mod
K_{p})&\text{if $|A|=\left\lfloor{m(V)/K_{p}}\right\rfloor<m(V)/K_{p}$,}\\\
+\infty&\text{otherwise.}\end{cases}\end{cases}$

First, suppose that $\alpha=\alpha^{(1)}$. Let $u\in A$ be a vertex such that
$\alpha=m(u)$. Then, we have that $u\in\mathcal{Z}\not=\emptyset$. Thus, we
have that $u\in A\subseteq V-\mathcal{Z}\subseteq V-\\{u\\}$, a contradiction.

Next, suppose that $\alpha=\alpha^{(2)}$. Let $X\subseteq V-A$ be a set such
that $\alpha=K_{p}-p(X)$. Then, we have that
$p^{\prime\prime}(X)=p(X)=K_{p}-\alpha=K_{p^{\prime\prime}}.$ Here, the first
equality is because $X\subseteq V-A$ and the final equality is by Lemma
5.4(b). Thus, the set $X$ is a $p^{\prime\prime}$-maximizer and hence $X\cap
A\not=\emptyset$ since the set $A$ satisfies Lemma 5.1(1) with respect to the
functions $p^{\prime\prime}$ and $m^{\prime\prime}$, a contradiction to
$X\subseteq V-A$.

Next, suppose $\alpha=\alpha^{(3)}$. Let $u\in V-A$ be a vertex such that
$\alpha=K_{p}-m(u)$. Then, we have that
$m^{\prime\prime}(u)=m(u)=K_{p}-\alpha=K_{p^{\prime\prime}}$. Here, the first
equality is because $u\in V-A$, and the final equality is by Lemma 5.4(b).
Thus, $m^{\prime\prime}(u)=K_{p^{\prime\prime}}$ and consequently $u\in A$
since the set $A$ satisfies Lemma 5.1(2) with respect to the functions
$p^{\prime\prime}$ and $m^{\prime\prime}$, a contradiction to $u\in V-A$.

Next, suppose that $\alpha=\alpha^{(4)}$. Let $X\subseteq V$ be such that
$|A\cap X|\geq 2$ and $\alpha=\left\lfloor{\frac{m(X)-p(X)}{|A\cap
X|-1}}\right\rfloor$. First, we consider the case where
$\alpha=\frac{m(X)-p(X)}{|A\cap X|-1}$. Then, we have that
$m^{\prime\prime}(X)=m(X)-\alpha|A\cap X|=p(X)-\alpha=p^{\prime\prime}(X)$,
where the first and final equalities are because $|A\cap X|\geq 1$. This gives
us the required contradiction as follows: $p^{\prime\prime}(X)-1\leq
m^{\prime\prime}(X)-|A\cap X|=p^{\prime\prime}(X)-|A\cap
X|<p^{\prime\prime}(X)-1$, a contradiction. Here, the first inequality is
because the set $A$ satisfies Lemma 5.1(3) with respect to the functions
$p^{\prime\prime}$ and $m^{\prime\prime}$ and the final inequality is because
$|A\cap X|\geq 2$. Next, we consider the case where
$\alpha<\frac{m(X)-p(X)}{|A\cap X|-1}$. Then, it follows that
$\alpha+1>\frac{m(X)-p(X)}{|A\cap X|-1}$. Rewriting this shows that
$p(X)-\alpha+|A\cap X|-1>m(X)-\alpha|A\cap X|$. Consequently,
$m^{\prime\prime}(X)=m(X)-\alpha|A\cap X|<p(X)-\alpha+|A\cap
X|-1=p^{\prime\prime}(X)+|A\cap X|-1$. This gives us the required
contradiction as follows: $p^{\prime\prime}(X)-1\leq
m^{\prime\prime}(X)-|A\cap X|<p^{\prime\prime}(X)-1$, a contradiction. Here,
the first inequality is because the set $A$ satisfies Lemma 5.1(3) with
respect to the functions $p^{\prime\prime}$ and $m^{\prime\prime}$.

Next, suppose that $\alpha=\alpha^{(5)}$. By Lemma 5.6, we have that
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}$ is an integer and
$m^{\prime\prime}(V-\mathcal{Z})/K_{p^{\prime\prime}}\neq|A|$. This
contradicts Lemma 5.1(4) with respect to the functions $p^{\prime\prime}$ and
$m^{\prime\prime}$. ∎

###  5.3 Number of Recursive Calls of Algorithm 2 with
$\alpha\in\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$

In this section, we bound the number of recursive calls of Algorithm 2 that
witness $\alpha\in\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$.
The main result of this section is Corollary 5.1 which we show at the end of
the section.

##### Notation.

We first set up some convenient notation that will be used in the remainder of
this section as well as in subsequent sections. By Lemma 5.5, the number of
recursive calls made by the algorithm is finite. We will use $\ell$ to denote
the depth of recursion of the algorithm. We will refer to the recursive call
at depth $i$ as _recursive call $i$_ or the _$i^{th}$ recursive call_. Let
$V_{i}$ denote the ground set at the start of recursive call $i$, and
$p_{i}\mathrel{\mathop{\mathchar 58\relax}}2^{V_{i}}\rightarrow\Z$,
$m_{i}\mathrel{\mathop{\mathchar 58\relax}}V_{i}\rightarrow\Z_{+}$, and
$J_{i}\subseteq V_{i}$ denote the inputs to recursive call $i$. Furthermore,
let
$A_{i},\alpha_{i},\alpha^{(1)}_{i},\alpha^{(2)}_{i},\alpha^{(3)}_{i},\alpha^{(4)}_{i},\alpha^{(5)}_{i},\mathcal{Z}_{i},p^{\prime}_{i},m^{\prime}_{i}$
denote the quantities
$A,\alpha,\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)},\mathcal{Z},p^{\prime},m^{\prime}$
defined by Algorithm 2 at recursive call $i$. For notational convenience, we
define $\mathcal{Z}_{\ell},\calD_{\ell}=\emptyset$. Finally, let
$\left(H_{i}=\left(V_{i},E_{i}\right),w_{i}\right)$ denote the hypergraph
returned by recursive call $i$.

We note that Lemma 5.4 and induction on the recursion depth $i$ immediately
imply the following lemma which says that for every $i\in[\ell]$, the input
tuple $(p_{i},m_{i},J_{i})$ satisfies the hypothesis of Lemma 5.5.

######  Lemma 5.8.

Consider a feasible execution of Algorithm 2 with $\ell\in\Z_{+}$ recursive
calls. For every $i\in[\ell]$, suppose that the input to the $i^{th}$
recursive call of Algorithm 2 is a tuple $(p_{i},m_{i},J_{i})$, where
$J_{1}\subseteq V_{1}$ is an arbitrary set, and the functions
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ are such that
$m_{1}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and $m_{1}(u)\leq K_{p_{1}}$
for every $u\in V_{1}$. Then, for every $i\in[\ell]$, we have that the
function $p_{i}\mathrel{\mathop{\mathchar 58\relax}}2^{V_{i}}\rightarrow\Z$
and positive function $m_{i}\mathrel{\mathop{\mathchar
58\relax}}V_{i}\rightarrow\Z_{+}$ satisfy $m_{i}(X)\geq p_{i}(X)$ for all
$X\subseteq V_{i}$ and $m_{i}(u)\leq K_{p_{i}}$ for all $u\in V_{i}$.

##### Set Families.

We now define certain set families that will be useful in the analysis. We
recall that $\mathcal{Z}_{i}=\\{u\in V_{i}\mathrel{\mathop{\mathchar
58\relax}}m_{i}^{\prime}(u)=0\\}$. We let the family $\calZ_{\leq
i}\coloneqq\cup_{j\in[i]}\mathcal{Z}_{i}$. We also let
$\calD_{i}\coloneqq\\{u\in V_{i}\mathrel{\mathop{\mathchar
58\relax}}m_{i}(u)=K_{p_{i}}\\}$ and $\calD_{i}^{\prime}\coloneqq\\{u\in
V_{i}\mathrel{\mathop{\mathchar
58\relax}}m_{i}^{\prime}(u)=K_{p^{\prime}_{i}}\\}$. We use $\calF_{i}$ to
denote the families of _minimal_ $p_{i}$-maximizers. Lemma 5.9 below shows the
progression of minimal $p_{i}$-maximizer families across recursive calls of an
execution of Algorithm 2. We will also be interested in families of all
minimal maximizers of the input functions witnessed by the algorithm up to a
given recursive call. Formally, we define the family $\calF_{\leq
i}\coloneqq\cup_{j\in[i]}\calF_{j}$. Lemma 5.10 below summarizes the
properties of the stated families that will help in subsequent analysis.

######  Lemma 5.9.

Consider a feasible execution of Algorithm 2 with $\ell\in\Z_{+}$ recursive
calls. For every $i\in[\ell]$, suppose that the input to the $i^{th}$
recursive call of Algorithm 2 is a tuple $(p_{i},m_{i},J_{i})$, where
$J_{1}\subseteq V_{1}$ is an arbitrary set, and the functions
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ are such that
$m_{1}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and $m_{1}(u)\leq K_{p_{1}}$
for every $u\in V_{1}$. Then, for every $i\in[\ell-1]$ we have the following:

  1. (a)

if $Y\subseteq V_{i}$ is a $p_{i}$-maximizer, then $Y$ is also a
$p_{i}^{\prime}$-maximizer, and

  2. (b)

if $Y\subseteq V_{i}$ is a $p_{i}^{\prime}$-maximizer such that
$Y-\mathcal{Z}_{i}\not=\emptyset$, then $Y-\mathcal{Z}_{i}$ is a
$p_{i+1}$-maximizer.

###### Proof.

By Lemma 5.4 (a), (c), and (d), we have that for every $i\in[\ell]$, the
function $m_{i}\mathrel{\mathop{\mathchar 58\relax}}V_{i}\rightarrow\Z$ is a
positive function, and the functions $p_{i}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{i}}\rightarrow\Z$ and $m_{i}$ are such that $m_{i}(X)\geq
p_{i}(X)$ for every $X\subseteq V_{i}$ and $m_{i}(u)\leq K_{p_{i}}$ for every
$u\in V_{i}$. We prove both claims below for a fixed $i\in[\ell]$.

  1. (a)

Let $Y\subseteq V_{i}$ be a $p_{i}$-maximizer. By Lemma 5.1(1), the set
$A_{i}$ is a transversal for the family of $p_{i}$-maximizers. Thus, we have
that
$p_{i}^{\prime}(Y)=p_{i}(Y)-\alpha_{i}=K_{p_{i}}-\alpha_{i}=K_{p_{i}^{\prime}}$,
where the first equality is because $A_{i}\cap Y\not=\emptyset$ and the third
equality is by Lemma 5.3(b).

  2. (b)

Let $Y\subseteq V_{i}$ be a $p_{i}^{\prime}$-maximizer such that
$Y-\mathcal{Z}_{i}\neq\emptyset$. We have the following:

$K_{p_{i+1}}\geq p_{i+1}(Y-\mathcal{Z}_{i})=\max\\{p_{i}^{\prime}(Y\cup
R)\mathrel{\mathop{\mathchar 58\relax}}R\subseteq\mathcal{Z}_{i}\\}\geq
p_{i}^{\prime}(Y)=K_{p_{i}^{\prime}}=K_{p_{i+1}},$

where the final equality is by Lemma 5.4(b). Thus, all inequalities are
equations and we have that $p_{i+1}(Y-\mathcal{Z}_{i})=K_{p_{i+1}}$.

∎

######  Lemma 5.10.

Consider a feasible execution of Algorithm 2 with $\ell\in\Z_{+}$ recursive
calls. For every $i\in[\ell]$, suppose that the input to the $i^{th}$
recursive call of Algorithm 2 is a tuple $(p_{i},m_{i},J_{i})$, where
$J_{1}\subseteq V$ is an arbitrary set, and the functions
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ are such that
$m_{1}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and $m_{1}(u)\leq K_{p_{1}}$
for every $u\in V_{1}$. Then, for every $i\in[\ell-1]$ we have the following:

  1. (a)

$\mathcal{Z}_{\leq i}\subseteq\mathcal{Z}_{\leq i+1}$; furthermore,
$\alpha_{i}=\alpha_{i}^{(1)}$ if and only if $\mathcal{Z}_{i}\not=\emptyset$
(i.e., $\mathcal{Z}_{\leq i}\subsetneq\mathcal{Z}_{\leq i+1}$),

  2. (b)

$\calF_{\leq i}\subseteq\calF_{\leq i+1}$; furthermore, if
$\alpha_{i}=\alpha_{i}^{(2)}<\alpha_{i}^{(1)}$, then $\calF_{\leq
i}\subsetneq\calF_{\leq i+1}$,

  3. (c)

$\calD_{i}\subseteq\calD_{i}^{\prime}\subseteq\calD_{i+1}$; furthermore, if
$\alpha_{i}=\alpha_{i}^{(3)}$, then $\calD_{i}\subsetneq\calD_{i}^{\prime}$,
and

  4. (d)

if $\calF_{\leq i}=\calF_{\leq i+1}$ and $\mathcal{Z}_{i}=\emptyset$, then
$\calF_{i}=\calF_{i+1}$.

###### Proof.

By Lemma 5.4 (a), (c), and (d), we have that for every $i\in[\ell]$, the
function $m_{i}\mathrel{\mathop{\mathchar 58\relax}}V_{i}\rightarrow\Z$ is a
positive function, and the functions $p_{i}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{i}}\rightarrow\Z$ and $m_{i}$ are such that $m_{i}(X)\geq
p_{i}(X)$ for every $X\subseteq V_{i}$ and $m_{i}(u)\leq K_{p_{i}}$ for every
$u\in V_{i}$. We prove each claim separately below.

  1. (a)

We have that $\calZ_{\leq i}\subseteq\calZ_{\leq i+1}$ by definition. We now
show the second part of the claim. For the forward direction, suppose that
$\alpha_{i}=\alpha_{i}^{(1)}$. Let $u\in A_{i}$ be a vertex such that
$m_{i}(u)=\alpha_{i}$ (such a vertex exists since
$\alpha_{i}=\alpha_{i}^{(1)}$). Then, we have that
$m_{i}^{\prime}(u)=m_{i}(u)-\alpha_{i}\chi_{A_{i}}(u)=0$. Thus,
$u\in\mathcal{Z}_{i}$. The reverse direction of the claim follows because the
function $m$ is a positive function.

  2. (b)

We note that $\calF_{\leq i}\subseteq\calF_{\leq i+1}$ follows by definition.
We now show the second part of the claim. Suppose that
$\alpha_{i}=\alpha_{i}^{(2)}<\alpha_{i}^{(1)}$. Then by part (a) of the
current lemma, we have that $\mathcal{Z}_{i}=\emptyset$, and consequently
$p_{i}^{\prime}=p_{i+1}$ by the definition of the two functions. We consider
the family $\calF_{i}^{\prime}$ of minimal $p_{i}^{\prime}$-maximizers. By
Lemma 5.9(a), we have that $\calF_{i}\subseteq\calF_{i}^{\prime}=\calF_{i+1}$,
and thus, $\calF_{\leq i}\subseteq\calF_{\leq
i}\cup\calF_{i}^{\prime}=\calF_{\leq i+1}$, where the equalities in both the
previous expressions are because $p_{i}^{\prime}=p_{i+1}$. We now show that
the first inclusion is strict. For convenience, we let $\calF_{\leq
i}^{\prime}\coloneqq\calF_{\leq i}\cup\calF_{i}^{\prime}$. By way of
contradiction, suppose that $\calF_{\leq i}=\calF_{\leq i}^{\prime}$. Let
$X\subseteq V_{i}-A_{i}$ be a set such that
$\alpha_{i}=\alpha_{i}^{(2)}=K_{p_{i}}-p_{i}(X)$ (such a set exists since
$\alpha_{i}=\alpha_{i}^{(2)}$). Then, we have that
$p_{i}^{\prime}(X)=p_{i}(X)=K_{p_{i}}-\alpha_{i}^{(2)}=K_{p_{i}^{\prime}}.$
Here, the first equality is because $X\subseteq V_{i}-A_{i}$, the second
equality is because our choice of $X$ satisfies
$\alpha_{i}^{(2)}=K_{p_{i}}-p_{i}(X)$, and the final inequality is by Lemma
5.3(b). Thus, the set $X$ is a $p_{i}^{\prime}$-maximizer. Furthermore, the
set $X$ is not a $p_{i}$-maximizer since the set $A_{i}$ is a transversal for
the family of $p_{i}$-maximizers by Lemma 5.1(1), but $A_{i}\cap X=\emptyset$.
Consequently, there exists a set $Y\subseteq X$ such that
$Y\in\calF_{i}^{\prime}-\calF_{i}$. Since $\calF_{\leq i}=\calF_{\leq
i}^{\prime}$, we have that $Y\in\calF_{\leq i-1}$. In particular, there exists
a recursive call $j\in[i-1]$ such that $Y\in\calF_{j}$. Since $Y\subseteq
V_{i}$, by Lemma 5.9(a), (b) and induction on $j$, we have that
$Y\in\calF_{i}$. Thus, the set $Y$ is a $p_{i}$-maximizer and consequently
$A_{i}\cap Y\not=\emptyset$ by Lemma 5.1(1), a contradiction to $A_{i}\cap
X=\emptyset$.

  3. (c)

First, we show that $\calD_{i}\subseteq\calD_{i}^{\prime}$ for every
$i\in[\ell]$. Let $u\in\calD_{i}$. Then we have the following:

$m_{i}^{\prime}(u)=m_{i}(u)-\alpha_{i}\chi_{A_{i}}(u)=K_{p_{i}}-\alpha_{i}\chi_{A_{i}}(u)=K_{p_{i}}-\alpha_{i}=K_{p_{i}^{\prime}}.$

Here, the second equality is because $u\in\calD_{i}$, the third equality is
because $\calD_{i}\subseteq A_{i}$ by Lemma 5.1(2), and the final equality is
by Lemma 5.3(b). Thus, $u\in\calD_{i}^{\prime}$ and we have that
$\calD_{i}\subseteq\calD_{i}^{\prime}$. Next, we show that
$\calD_{i}^{\prime}\subseteq\calD_{i+1}$. Let $u\in\calD_{i}^{\prime}$. We
note that if $u\in\mathcal{Z}_{i}$, then we have that
$0=m_{i}^{\prime}(u)=K_{p_{i}^{\prime}}$, and thus $i=\ell$, contradicting
$i\in[1,\ell-1]$. Thus, $u\not\in\mathcal{Z}_{i}$, i.e. $u\in V_{i+1}$. Then,
we have that $m_{i+1}(u)=m_{i}^{\prime}(u)=K_{p_{i}^{\prime}}=K_{p_{i+1}}$,
where the final equality is by Lemma 5.4(b). Thus, $u\in\calD_{i+1}$ and we
have that $\calD_{i}^{\prime}\subseteq\calD_{i+1}$.

We now show the second part of the claim. Suppose that
$\alpha_{i}=\alpha_{i}^{(3)}$ and let $v\in V_{i}-A_{i}$ be a vertex such that
$\alpha_{i}=K_{p_{i}}-m_{i}(v)$ (such a vertex exists since
$\alpha_{i}=\alpha_{i}^{(3)}$). Then, we have that:

$m_{i}^{\prime}(v)=m_{i}(v)-\alpha_{i}\chi_{A_{i}}(v)=m_{i}(v)=K_{p_{i}}-\alpha_{i}=K_{p_{i+1}}.$

Here, the second and third equalities are by the choice of $v$ and the final
equality is by Lemma 5.3(b). Thus, $v\in\calD_{i+1}\backslash\calD_{i}$.

  4. (d)

We note that since $\mathcal{Z}_{i}=\emptyset$, the function
$p_{i}^{\prime}=p_{i+1}$. Consequently, $\calF_{i+1}=\calF_{i}^{\prime}$ and
$\calF_{\leq i+1}=\calF_{\leq i}^{\prime}$. Since $\calF_{\leq
i+1}=\calF_{\leq i}$, we have that $\calF_{\leq i}=\calF_{\leq i}^{\prime}$.
By Lemma 5.9(a), we have that $\calF_{i}\subseteq\calF_{i}^{\prime}$. Thus, it
suffices to show the reverse inclusion $\calF_{i}^{\prime}\subseteq\calF_{i}$
By way of contradiction, let $X\in\calF_{i}^{\prime}-\calF_{i}\not=\emptyset$.
Since $\calF_{i}^{\prime}\subseteq\calF_{\leq i}^{\prime}=\calF_{\leq i}$, we
have that $X\in\calF_{\leq i}$. By definition of the family $\calF_{\leq i}$
and our choice of the set $X$, there exists $j\in[i-1]$ and
$Y\in\calF_{j}\cup\calF_{j}^{\prime}$ such that $Y\cap V_{i}=X$. By Lemma
5.9(a), (b) and induction on $j$, we have that $X\in\calF_{i}$, a
contradiction to the choice of set $X$.

∎

We now show the main result of the section which says that the number of
recursive calls of a feasible execution of Algorithm 2 for which
$\alpha\in\left\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\right\\}$
is at most $|\calF_{\leq\ell}|+2|V|+1$. We derive this as a consequence of
Lemma 5.10.

######  Corollary 5.1.

Consider a feasible execution of Algorithm 2 with $\ell\in\Z_{+}$ recursive
calls. Suppose that the input to Algorithm 2 is a tuple $(p_{1},m_{1},J_{1})$,
where $J_{1}\subseteq V$ is an arbitrary set, and the functions
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ are such that
$m_{1}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and $m_{1}(u)\leq K_{p_{1}}$
for every $u\in V_{1}$. Then, we have that

$\left|\left\\{i\in[\ell-1]\mathrel{\mathop{\mathchar
58\relax}}\alpha_{i}\in\left\\{\alpha_{i}^{(1)},\alpha_{i}^{(2)},\alpha_{i}^{(3)},\alpha_{i}^{(5)}\right\\}\right\\}\right|\leq\left|\calF_{\leq\ell}\right|+2|V|+1.$

###### Proof.

We first show that the number of iterations $i$ for which
$\alpha_{i}=\alpha_{i}^{(5)}$ is at most one. Let $i\in[\ell-1]$ be the least
index such that $\alpha_{i}=\alpha_{i}^{(5)}$. Then, by Lemma 5.6, we have
that $m_{i}(V_{i})/K_{p_{i}}\not\in Z$ and one of the following holds: either
$K_{p_{i+1}}=0$ or $m_{i+1}(V_{i+1})/K_{p_{i+1}}\in\Z$. If $K_{p_{i+1}}=0$,
then $i=\ell-1$ and this is the only iteration where
$\alpha_{i}=\alpha_{i}^{(5)}$. If $m_{i+1}(V_{i+1})/K_{p_{i+1}}\in\Z$, then
$\alpha_{j}^{(5)}=\infty$ for every $j\geq i+1$ by definition and
consequently, $\alpha\neq\alpha_{j}^{(5)}$ for every $j\geq i+1$.

By the above arguments, it suffices to show that the number of iterations $i$
for which
$\alpha_{i}\in\\{\alpha_{i}^{(1)},\alpha_{i}^{(2)},\alpha_{i}^{(3)}\\}$ is at
most $\left|\calF_{\leq\ell}\right|+2|V|$. For this, we define a potential
function $\phi\mathrel{\mathop{\mathchar 58\relax}}[\ell]\rightarrow\Z_{\geq
0}$ as follows: for every $i\in[\ell]$,

$\phi(i)\coloneqq|\mathcal{Z}_{\leq i}|+|\calF_{\leq i}|+|\calD_{i}|.$

By Lemma 5.10, we have that the function $\phi$ is non-decreasing as each of
the three terms of $\phi$ are non-decreasing. By Lemma 5.10, we also have that
if
$\alpha_{i}\in\left\\{\alpha_{i}^{(1)},\alpha_{i}^{(2)},\alpha_{i}^{(3)}\right\\}$,
then $\phi(i)<\phi(i+1)$. In particular, we have that the number of recursive
calls of the algorithm with
$\alpha\in\left\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)}\right\\}$ is at most
$\phi(\ell)-\phi(0)\leq|\mathcal{Z}_{\leq\ell}|+|\calF_{p_{\leq\ell}}|+|\calD_{\ell}|\leq
2|V|+|\calF_{{\leq\ell}}|$. ∎

###  5.4 Feasibility of Execution for Skew-supermodular Functions

In this section, we show that the execution of Algorithm 2 is feasible under a
skew-supermodularity assumption on the input function. We recall that a call
to Algorithm 2 is feasible if the input functions $p$ and $m$ are such that
the polyhedron $Q(p,m)$ is non-empty and integral. Moreover, the execution of
Algorithm 2 is feasible if for every recursive call to the algorithm during
its execution, either Algorithm 2 is in its base case or recursive call is
feasible Bernáth and Király showed the following result.

######  Lemma 5.11 ([8]).

Let $q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be skew-
supermodular functions and $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ be the function defined as
$p(X)\coloneqq\max\\{q(X),r(X)\\}$ for every $X\subseteq V$. Furthermore, let
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ be a non-
negative function satisfying $m(X)\geq p(X)$ for every $X\subseteq V$ and
$m(u)\leq K_{p}$ for every $u\in V$. Then, the polyhedron $Q(p,m)$ is a non-
empty integral polyhedron.

Using Lemma 5.11 in conjunction with Lemma 5.8 leads to the following
corollary showing feasibility of the execution of Algorithm 2.

######  Corollary 5.2.

Let $q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be skew-
supermodular functions. Suppose that the input to Algorithm 2 is a tuple
$(p,m,J)$, where $J\subseteq V$ is an arbitrary set,
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a function
defined by $p(X)\coloneqq\max\\{q(X),r(X)\\}$ for every $X\subseteq V$ with
$K_{p}>0$ and $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a
positive integer-valued function such that $m(X)\geq p(X)$ for every
$X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$. Let
$\mathcal{Z},(H_{0},w_{0}),p^{\prime\prime},m^{\prime\prime},J^{\prime\prime}$
be as defined by Algorithm 2. Then, the input tuple
$(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$ for the subsequent
recursive call in the execution of the algorithm either has
$K_{p^{\prime\prime}}=0$ or satisfies the following properties:

  1. (1)

the functions $q^{\prime\prime}$ and $r^{\prime\prime}$ defined by
$q^{\prime\prime}\coloneqq{(q-b_{(H_{0},w_{0})})}/_{\mathcal{Z}}$ and
$r^{\prime\prime}\coloneqq{(r-b_{(H_{0},w_{0})})}/_{\mathcal{Z}}$, where
$(H_{0},w_{0}),\mathcal{Z}$ are as defined by Algorithm 2, are skew-
supermodular; furthermore
$p^{\prime\prime}(X)=\max\\{q^{\prime\prime}(X),r^{\prime\prime}(X)\\}$ for
every $X\subseteq V$,

  2. (2)

$m^{\prime\prime}$ is a positive integer-valued function,

  3. (3)

$m^{\prime\prime}(X)\geq p^{\prime\prime}(X)$ for every $X\subseteq V$,

  4. (4)

$m^{\prime\prime}(u)\leq K_{p^{\prime\prime}}$ for every $u\in
V^{\prime\prime}$, and

  5. (5)

$Q(p^{\prime\prime},m^{\prime\prime})$ is a non-empty integral polyhedron.

In particular, the execution of Algorithm 2 on the input tuple $(p,m,J)$ is a
feasible execution with finite recursion depth.

###### Proof.

We note that the function $b_{(H_{0},w_{0})}$ is submodular, and consequently,
the functions $q^{\prime\prime}$ and $r^{\prime\prime}$ are skew-supermodular
by definition. Let $V^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}=V-\mathcal{Z}$. Consider a set $X\subseteq V^{\prime\prime}$. Then,
we have the following:

$\displaystyle p^{\prime\prime}(X)$
$\displaystyle={(p-b_{(H_{0},w_{0})})}/_{\mathcal{Z}}(X)$
$\displaystyle={\left(\max\\{q,r\\}-b_{(H_{0},w_{0})}\right)}/_{\mathcal{Z}}(X)$
$\displaystyle={\left(\max\\{q-b_{(H_{0},w_{0})},r-b_{(H_{0},w_{0})}\\}\right)}/_{\mathcal{Z}}(X)$
$\displaystyle=\max\\{q^{\prime\prime}(X),r^{\prime\prime}(X)\\},$

where the first equality is by Step 9. Thus, property (1) of the claim holds.
Furthermore, properties (2), (3) and (4) of the claim hold by Lemma 5.4.
Finally, property (5) of the claim holds by Lemma 5.11 and the previously
shown properties (2), (3) and (4) of the claim.

We now show that the execution of Algorithm 2 on the input tuple $(p,m,J)$ is
a feasible execution with finite recursion depth using (reverse) induction on
the value $K_{p}$. For the base case, suppose that $K_{p}=0$. Then, we have
that $V=\emptyset$ since $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function with $m(u)\leq K_{p}$ for
every $u\in V$. Thus, Step 1 returns the empty hypergraph and the claim holds.
For the induction step, suppose that $K_{p}>0$. We recall that
$K_{p^{\prime\prime}}=K_{p}-\alpha\leq K_{p}-1$, where the equality is by
Lemma 5.4 and the inequality is by Lemma 5.2. By the inductive hypothesis, we
have that the execution of Algorithm 2 on the input tuple
$(p^{\prime\prime},m^{\prime\prime},J^{\prime\prime})$, where
$J^{\prime\prime}\subseteq V^{\prime\prime}$ is the set defined by Algorithm
2, is a feasible execution with finite recursion depth. Furthermore, by Lemma
5.11, $Q(p,m)$ is a non-empty integral polyhedron. Consequently the execution
of Algorithm 2 on the input tuple $(p,m,J)$ is also feasible execution with
finite recursion depth. ∎

Lemma 5.11 implies the following for skew-supermodular functions.

######  Lemma 5.12 ([8]).

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function and $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ be a non-negative function satisfying
$m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in
V$. Then, the polyhedron $Q(p,m)$ is a non-empty integral polyhedron.

Using Lemma 5.12 in conjunction with Lemma 5.8 leads to the following
corollary (similar to the proof of Corollary 5.2).

######  Corollary 5.3.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is an arbitrary set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a skew-supermodular function with $K_{p}>0$,
and $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a positive
integer-valued function such that $m(X)\geq p(X)$ for every $X\subseteq V$ and
$m(u)\leq K_{p}$ for every $u\in V$. Then, the input
$(p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V^{\prime\prime}}\rightarrow\Z,m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V^{\prime\prime}\rightarrow\Z,J^{\prime\prime}\subseteq
V^{\prime\prime})$ for every recursive call in the execution of the algorithm
either has $K_{p^{\prime\prime}}=0$ or satisfies the following properties:

  1. (1)

$p^{\prime\prime}$ is skew-supermodular,

  2. (2)

$m^{\prime\prime}$ is a positive integer-valued function,

  3. (3)

$m^{\prime\prime}(X)\geq p^{\prime\prime}(X)$ for every $X\subseteq V$,

  4. (4)

$m^{\prime\prime}(u)\leq K_{p^{\prime\prime}}$ for every $u\in
V^{\prime\prime}$, and

  5. (5)

$Q(p^{\prime\prime},m^{\prime\prime})$ is a non-empty integral polyhedron.

In particular, the execution of the algorithm is a feasible execution with
finite recursion depth.

###  5.5 Run-time for Skew-supermodular Functions

In this section, we bound the run-time of Algorithm 2 for skew-supermodular
functions assuming a bound on the recursion depth of the algorithm. Lemma 5.16
and Lemma 5.17 are the main lemmas of this section.

In order to show that each recursive call of Algorithm 2 can be implemented in
polynomial time, we will require the ability to solve certain optimization
problems in polynomial time. In the next two lemmas, we summarize these
optimization problems and show that they can be solved in polynomial time. The
proofs of these lemmas use combinations of several known tools in submodular
minimization. We note that Lemma 5.14 below does not require the input
function $p$ to be skew-supermodular while Lemma 5.13 below requires the input
functions $q$ and $r$ to be skew-supermodular.

Lemma 5.13 concerns optimizing over the polyhedron $Q(p,m)$. We note that
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ is the separation oracle for
constraint (iv) of the polyhedron $Q(p,m)$. Consequently, given access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$, we can optimize over the
polyhedron $Q(p,m)$ in _weakly_ polynomial time using the ellipsoid algorithm.
The following lemma shows that given access to
${q}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$, where functions
$q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ are _skew-
supermodular_ , we can optimize over the Q-polyhedron associated with the
function $p$ defined as $p(X)\mathrel{\mathop{\mathchar
58\relax}}=\max\\{q(X),r(X)\\}$ for every $X\subseteq V$ in _strongly_
polynomial time. We defer the proof of the lemma to Section B.2.

######  Lemma 5.13.

Let $q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be skew-
supermodular functions and let $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ be the function defined as
$p(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{q(X),r(X)\\}$ for every
$X\subseteq V$. Then, the following optimization problem can be solved in
$\poly(|V|)$ time using $\poly(|V|)$ queries to
${q}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$: for a given non-negative
function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ such
that $Q(p,m)\neq\emptyset$ and a given cost vector $c\in\R^{V}$, find an
extreme point optimum solution to the following linear program:

$\max\left\\{\sum_{u\in V}c_{u}x_{u}\mathrel{\mathop{\mathchar 58\relax}}x\in
Q(p,m)\right\\}.$

Lemma 5.14 defines a ratio-maximization problem and shows that it can be
solved in strongly polynomial time using polynomial number of maximization-
oracle queries. This will be helpful in computing the value of $\alpha^{(4)}$
in Algorithm 2 Step 5. We defer the proof of the lemma to Section B.3.

######  Lemma 5.14.

For a function $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, the
following optimization problem can be solved in $\poly(|V|)$ time using
$\poly(|V|)$ queries to ${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$: for
a given vector $y\in\R^{V}$ and a given set $A\subseteq V$, compute a set $Z$
satisfying $|A\cap Z|\geq 2$ that maximizes $(p(Z)-y(Z))/(|A\cap Z|-1)$ i.e.,

$\arg\max\left\\{\frac{p(Z)-y(Z)}{|A\cap Z|-1}\mathrel{\mathop{\mathchar
58\relax}}|A\cap Z|\geq 2\right\\}.$

The next lemma shows how the function input to an arbitrary recursive call of
Algorithm 2 is related to the function input to the first recursive call. We
will use this expression in proving the main lemma of the section. The proof
of the lemma follows by induction on the recursion depth and is exactly the
same as that of Lemma 4.8. We omit the proof for brevity.

######  Lemma 5.15.

Suppose that the input to Algorithm 2 is a tuple $(p_{1},m_{1})$, where
$p_{1}\mathrel{\mathop{\mathchar 58\relax}}2^{V_{1}}\rightarrow\Z$ and
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}V_{1}\rightarrow\Z_{+}$ are
functions such that $m_{1}(X)\geq p_{1}(X)$ for all $X\subseteq V_{1}$ and
$m_{1}(u)\leq K_{p_{1}}$ for all $u\in V_{1}$. Let $\ell\in\Z_{+}$ be the
number of recursive calls witnessed by the execution of Algorithm 2. For
$i\in[\ell]$, let $(p_{i},m_{i})$ be the input tuple to the $i^{th}$ recursive
call; moreover, for $i\in[\ell-1]$, let
$\mathcal{Z}_{i},(H^{i}_{0},w^{i}_{0})$ be as defined by Algorithm 2 for the
input $(p_{i},m_{i})$. Then, for each $i\in[\ell]$ we have that

$p_{i}={\left(p_{1}-\sum_{j\in[i-1]}b_{(\tilde{H}_{j},\tilde{w}_{j})}\right)}/_{\bigcup_{j\in[i-1]}\mathcal{Z}_{j}},$

where $(\tilde{H}_{0}^{i},\tilde{w}_{0}^{i})$ denotes the hypergraph obtained
by adding the vertices $\cup_{j\in[i-1]}\mathcal{Z}_{j}$ to the hypergraph
$(H^{i}_{0},w^{i}_{0})$.

We now bound the run-time of Algorithm 2 in terms of its recursion depth. In
subsequent sections, we will get strongly polynomial bounds on the recursion
depth of the Algorithm 2 when the input function $p$ is skew-supermodular (or
is defined to be the maximum of two skew-supermodular functions). Then, Lemma
5.16 (or respectively, Lemma 5.17) below will imply an overall strongly
polynomial runtime for Algorithm 2, given access to the appropriate function
maximization oracle for $p$.

######  Lemma 5.16.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where $J\subseteq
V$ is a set, $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a
skew-supermodular function, and $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive integer-valued function such that
$m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in
V$. Let $\ell\in\Z_{+}$ denote the recursion depth of Algorithm 2 on the input
tuple $(p,m,J)$ is $\ell$. Then, Algorithm 2 can be implemented to run in time
poly$(|V|,\ell)$ using poly$(|V|,\ell)$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. The run-
time includes the time to construct the hypergraphs used as input to the
queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Moreover,
for each query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, the
hypergraph $(G_{0},c_{0})$ used as input to the query has $|V|$ vertices and
$O(\ell)$ hyperedges.

###### Proof.

By Corollary 5.3, the execution of Algorithm 2 is a feasible execution and
$\ell$ is finite. For $i\in[\ell]$, let the tuple $(p_{i},m_{i},J_{i})$ denote
the input to the $i^{th}$ recursive call – we note that
$(p_{1},m_{1},J_{1})=(p,m,J)$. The next claim shows that all steps of
Algorithm 2 except for Steps 9 and 10 in the $i^{th}$ recursive call can be
implemented to run in $\poly(|V|,\ell)$ time and $\poly(|V|)$ number of
queries to ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

######  Claim 5.1.

All steps except for Steps 9 and 10 in the $i^{th}$ recursive call can be
implemented to run in $\poly(|V_{i}|)+O(\ell)$ time using $\poly(|V_{i}|)$
queries to ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. The run-time
includes the time to construct the inputs for the queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

###### Proof.

Step 3 can be implemented in $\poly(|V_{i}|)$ time using $\poly(|V_{i}|)$
queries to ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ since we can
find an extreme point optimum solution $y$ to the LP $\max\\{\sum_{u\in
J_{i}}y_{u}\mathrel{\mathop{\mathchar 58\relax}}y\in Q(p_{i},m_{i})\\}$ in
$\poly(|V_{i}|)$ time using $\poly(|V_{i}|)$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ by Lemma 5.13. Step 4 can
be implemented in $O(|V_{i}|)$ time by explicitly checking $y_{u}>0$ for every
$u\in V_{i}$. Next, we show that Step 5 can be implemented in poly$(|V_{i}|)$
time using poly$(|V_{i}|)$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. We note that the value
$K_{p_{i}}$ can be computed by querying
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,y_{0}\mathrel{\mathop{\mathchar
58\relax}}=\\{0\\}^{V_{i}})$. Then, the values $\alpha_{i}^{(1)}$,
$\alpha^{(3)}$, $\alpha^{(3)}$ and $\alpha^{(5)}$ can be computed in
$O(|V_{i}|)$ time as follows: $\alpha_{i}^{(1)}$ and $\alpha_{i}^{(3)}$ can be
computed by iterating over all vertices in $V_{i}$, $\alpha_{i}^{(2)}$ can be
computed by the single query
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=A,y_{0}\mathrel{\mathop{\mathchar 58\relax}}=\\{0\\}^{V_{i}})$, and
$\alpha^{(5)}$ can be computed by checking the relevant conditions. Moreover,
$\alpha^{(4)}$ can be computed in $\poly(|V_{i}|)$ time using $\poly(|V_{i}|)$
queries to ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ by Lemma 5.14.
Consequently, Step 5 can be implemented in in $\poly(|V_{i}|)$ time using
$\poly(|V_{i}|)$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. Steps 6, 7 and 8 can be
implemented in $O(|V_{i}|)$ time by iterating over $V_{i}$. We note that the
number of distinct hyperedges in the hypergraph obtained from recursion (Step
10) is at most $\ell-i$ since each recursive call adds at most one distinct
hyperedge to the returned. Thus, Steps 11 and 12 can be implemented in
$O(|V|+\ell)$ time. ∎

Next, we focus on the time to implement a query to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$.

######  Claim 5.2.

For disjoint subsets $S,T\subseteq V_{i}$ and a vector $y\in\Z^{V_{i}}$, the
answer to the query
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0}\mathrel{\mathop{\mathchar
58\relax}}=S,T_{0}\mathrel{\mathop{\mathchar
58\relax}}=T,y_{0}\mathrel{\mathop{\mathchar 58\relax}}=y)$ can be computed in
$O(|V_{1}|(|V_{1}|+\ell))$ time using at most $|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. The
run-time includes the time to construct the inputs for the queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, for each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, the
hypergraph $(G_{0},c_{0})$ used as input to the query has $|V_{1}|$ vertices
and $O(i)$ hyperedges.

###### Proof.

We prove the claim in two steps. In the first step, we will use the expression
for the function $p_{i}$ given by Lemma 5.15(b) to construct an answer for the
query ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S,T,y)$ using a
single query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$. In
the second step, we will obtain the desired runtime using
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ by
invoking Lemma 2.2.

For every $j\in[i]$, let $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ denote the
hypergraph obtained by adding the vertices $\cup_{k\in[j-1]}\mathcal{Z}_{k}$
to the hypergraph $(H^{k}_{0},w^{k}_{0})$. We now show the first step of the
proof via the following procedure. First, construct the hypergraph $(G,c)$ and
the vector $y_{1}\in\Z^{V_{1}}$, where $G\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j\in[i-1]}\tilde{H}_{0}^{j}$, $c\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j\in[i-1]},\tilde{w}_{0}^{j})$ and
$y_{1}(u)\mathrel{\mathop{\mathchar 58\relax}}=y_{0}(u)$ for every $u\in
V_{i}$, $y_{1}(u)\mathrel{\mathop{\mathchar 58\relax}}=0$ otherwise. Next,
obtain $(Z,p_{1}(Z))$ by querying
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,c),S,T,y_{1})$.
Finally, return $(Z-\cup_{j=1}^{i-1}\mathcal{Z}_{j},p(Z))$ as the answer to
the query ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S,T,y)$. We note
that correctness of the procedure is because
$p_{i}={\left(p_{1}-\sum_{j\in[i-1]}b_{(\tilde{H}_{j},\tilde{w}_{j})}\right)}/_{\bigcup_{j\in[i-1]}\mathcal{Z}_{j}}$
by Lemma 5.15(b).

We now show the second step of the proof. We observe that the hypergraph
$(G,c)$ constructed above has vertex set $V_{1}$ since for every $j\in[i-1]$,
the vertex set of $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ is contained in
$V_{1}$. Moreover, $(G,c)$ has at most $i-1$ distinct hyperedges because for
every $j\in[i-1]$, the hypergraph $(\tilde{H}_{0}^{j},\tilde{w}_{0}^{j})$ has
exactly $1$ hyperedge by Step 7. Consequently, by Lemma 2.2, the answer to the
query
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,c),S,T,y_{1})$
in the above procedure can be computed in $O(|V_{1}|(|V_{1}|+i))$ time using
$|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where
the runtime includes the time to construct the inputs to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$;
moreover, the hypergraph used as input to each
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ query
has at most $|V_{1}|$ vertices and $O(i)$ hyperedges. Finally, we note that
the construction of hypergraph $(G,c)$ and returning the (set, value) pair
returned by the above procedure can be implemented in $O(|V_{1}|(|V_{1}|+i))$
time and so the claim holds. ∎

We now complete the proof using the two claims above. By 5.1, all steps except
for Steps 9 and 10 in the $i^{th}$ recursive call can be implemented to run in
$\poly(|V_{i}|)+O(\ell)$ time using $\poly(|V_{i}|)$ queries to
${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$. By 5.2, an answer to a
single ${p_{i}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ query can be
computed in $O(|V_{1}|(|V_{1}|+\ell))$ time using at most $O(|V_{1}|)$ queries
to ${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Thus, all steps except for Steps 9 and 10 in the $i^{th}$ recursive call can
be implemented to run in $\poly(|V_{1}|,\ell)$ time and $\poly(|V_{1}|)$
queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. By
Claims 5.1 and 5.2, the run-time also includes the time to construct the
inputs for the queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, by 5.2, the hypergraph $(G_{0},c_{0})$ used as input to each
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ query
has $|V_{1}|$ vertices and $O(\ell)$ hyperedges.

We note that Steps 9 and 10 need not be implemented explicitly for the
purposes of the algorithm. Instead,
${p_{i+1}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ can be used to execute
all steps except for Steps 9 and 10 in the $(i+1)^{th}$ recursive call. We
note that 5.2 also enables us to answer a
${p_{i+1}}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ query in
$O(|V_{1}|(|V_{1}|+\ell))$ time using at most $|V_{1}|+1$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Thus,
we have shown that each recursive call can be implemented to run in
$\poly(|V_{1}|,\ell)$ time and $\poly(|V_{1}|)$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is on
an input hypergraph $(G_{0},c_{0})$ that has $|V_{1}|$ vertices and $O(\ell)$
hyperedges. Since there are $\ell$ recursive calls, Algorithm 2 can be
implemented to run in $\poly(|V_{1}|,\ell)$ time and
$\ell\cdot\poly(|V_{1}|)=\poly(|V_{1}|,\ell)$ queries to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ where
each query to
${p_{1}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is on
an input hypergraph $(G_{0},c_{0})$ that has $|V_{1}|$ vertices and $O(\ell)$
hyperedges. ∎

For simultaneous covering of two skew-supermodular functions, we have the
following lemma whose proof is similar to the proof of Lemma 5.16. We omit the
proof in the interests of brevity.

######  Lemma 5.17.

Let $q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be skew-
supermodular functions. Suppose that the input to Algorithm 2 is a tuple
$(p,m,J)$, where $J\subseteq V$ is a set, $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is the function defined as
$p(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{q(X),r(X)\\}$ for every
$X\subseteq V$, and $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$
is a positive integer-valued function such that $m(X)\geq p(X)$ for every
$X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$. Let $\ell\in\Z_{+}$
denote the recursion depth of Algorithm 2 on the input tuple $(p,m,J)$. Then,
Algorithm 2 can be implemented to run in time poly$(|V|,\ell)$ using
poly$(|V|,\ell)$ queries to
${q}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$. The run-
time includes the time to construct the hypergraphs used as input to the
queries to ${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$
and ${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.
Moreover, for each query to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, the
hypergraph $(G_{0},c_{0})$ used as input to the query has $|V|$ vertices and
$O(\ell)$ hyperedges.

###  5.6 Weak Cover of One Function with Linear Number of Near-Uniform
Hyperedges

In this section, we prove the following result.

See 1.8

We first describe how to prove Theorem 1.8 under the assumption that the input
function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a
_positive_ function. Under this extra assumption, we prove Theorem 1.8 by
running Algorithm 2 on the input instance $(p,m,\emptyset)$. By Corollary 5.3,
the execution of Algorithm 2 is a feasible execution with a finite recursion
depth. Furthermore, by Lemma 5.5, the hypergraph returned by Algorithm 2
satisfies properties (1), (2), (3) and (4) of Theorem 1.8. In this section, we
show that the hypergraph returned by Algorithm 2 also satisfies property (5)
of Theorem 1.8 and that the recursion depth of the algorithm is polynomial. By
Lemma 5.16 and the observation that each recursive call of the algorithm adds
at most one hyperedge, it suffices to bound the recursion depth of the
Algorithm 2 by $O(|V|)$.

The rest of this section is devoted to bounding the recursion depth. In
Section 5.6.1, we define a family of _cumulative projected maximal
$(p,m)$-tight sets_ (w.r.t. an execution of Algorithm 2) and prove certain
properties about this family that will be useful in bounding the recursion
depth. In Section 5.6.2, we define a notion of _good vectors_ and prove
certain properties which we subsequently use to bound the number of recursive
calls not considered by the bound in Corollary 5.1. In Section 5.6.3, we use
the tools which we developed in Section 5.6.1 and Section 5.6.2 to show that
the recursion depth of the algorithm is linear in the size of the ground set
(see Lemma 5.22). Thus, the returned hypergraph also satisfies property (5) of
Theorem 1.8. Lemma 5.22 and Lemma 5.16 together show that Algorithm 2 can be
implemented to run in _strongly polynomial_ time given the appropriate
function evaluation oracle (see Lemma 5.16). Corollary 5.3, Lemma 5.5, Lemma
5.22, and Lemma 5.16 complete the proof of Theorem 1.8 under the assumption
that the input function $m$ is positive.

We now briefly remark on how to circumvent the positivity assumption on the
input function $m$ in the above proof. We note that if
$\mathcal{Z}\coloneqq\\{u\in V\mathrel{\mathop{\mathchar
58\relax}}m(u)=0\\}\not=\emptyset$, then
${p}/_{\mathcal{Z}}\mathrel{\mathop{\mathchar
58\relax}}2^{V-\mathcal{Z}}\rightarrow\Z$ is a skew-supermodular function with
$K_{{p}/_{\mathcal{Z}}}\coloneqq\max\\{{p}/_{\mathcal{Z}}(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V-\mathcal{Z}\\}$ and
${m}\backslash_{\mathcal{Z}}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z_{+}$ is a _positive_ function such that
${m}\backslash_{\mathcal{Z}}(X)\geq{p}/_{\mathcal{Z}}(X)$ for every
$X\subseteq V-\mathcal{Z}$ and ${m}\backslash_{\mathcal{Z}}(u)\leq
K_{{p}/_{\mathcal{Z}}}$ for every $u\in V-\mathcal{Z}$ (i.e., the functions
${p}/_{\mathcal{Z}}$ and ${m}\backslash_{\mathcal{Z}}$ satisfy conditions (a)
and (b) of Theorem 1.8). Furthermore, we observe that a hypergraph satisfying
properties (1)–(5) of Theorem 1.8 for the functions ${p}/_{\mathcal{Z}}$ and
${m}\backslash_{\mathcal{Z}}$ also satisfies the five properties for the
functions $p$ and $m$. Thus, our final algorithm is to return the hypergraph
returned by Algorithm 2 on the instance
$({p}/_{\mathcal{Z}},{m}\backslash_{\mathcal{Z}},\emptyset)$. Finally,
${{p}/_{\mathcal{Z}}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$
can be implemented using
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ in
strongly polynomial time. This completes the proof of Theorem 1.8.

####  5.6.1 Laminarity of Projected Maximal Tight Sets Across Recursive Calls

In this section, we define $(p,m)$-tight set families and investigate how they
interact with the family of minimal $p$-maximizers. We will also investigate
the progression of these families during an execution of Algorithm 2. The
properties we prove in this section will be useful in the next section where
we bound the runtime of Algorithm 2 as well as the number of hyperedges in the
hypergraph returned by the algorithm.

######  Definition 5.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z$ be set functions. A set
$X\subseteq V$ is said to be _$(p,m)$ -tight_ if $p(X)=m(X)$. We let $T_{p,m}$
denote the family of $(p,m)$-tight sets and $\calT_{p,m}$ denote the family of
_inclusion-wise maximal_ $(p,m)$-tight sets.

The next lemma says that if $p$ is a skew-supermodular function and $m$ is
positive function satisfying $m(Z)\geq p(Z)$ for each $Z\subseteq V$, then the
family $\calT_{p,m}$ is disjoint. Furthermore, if the set $X\in\calT_{p,m}$ is
a maximal tight set w.r.t. functions $p$ and $m$, and the set $Y\in\calF_{p}$
is a minimal $p$-maximizer, then either the sets $X$ and $Y$ are disjoint, or
the maximal tight set $X$ is contained in the minimal $p$-maximizer $Y$.

######  Lemma 5.18.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function and $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ be a positive function such that $m(Z)\geq p(Z)$
for all $Z\subseteq V$. Then, we have the following:

  1. (a)

if $X,Y\in T_{p,m}$ such that $X\cap Y\not=0$, then $X\cap Y,X\cup Y\in
T_{p,m}$,

  2. (b)

the family $\calT_{p,m}$ is a disjoint set-family, and

  3. (c)

if $X\in\calT_{p,m}$ and $Y\in\calF_{p}$, then either $X\cap Y=\emptyset$ or
$X\subseteq Y$.

###### Proof.

We prove the claims below.

  1. (a)

If $X\subseteq Y$ or $Y\subseteq X$, the claim holds. Suppose that
$X-Y,Y-X\not=\emptyset$. We consider two cases based on the behavior of the
function $p$ at the sets $X$ and $Y$. First, suppose that $p(X)+p(Y)\leq
p(X-Y)+p(Y-X)$. We have the following:

$p(X)+p(Y)\leq p(X-Y)+p(Y-X)\leq m(X-Y)+m(Y-X)<m(X)+m(Y)=p(X)+p(Y),$

which gives a contradiction. Here, the second inequality is because $m(Z)\geq
p(Z)$ for every $Z\subseteq V$. The third inequality is because the function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow Z_{+}$ is a positive
function and $X\cap Y\not=\emptyset$. The final equality is because $X,Y\in
T_{p,m}$. Next, suppose that $p(X)+p(Y)\leq p(X\cup Y)+p(X\cap Y)$. We have
the following:

$p(X)+p(Y)\leq p(X\cup Y)+p(X\cap Y)\leq m(X\cup Y)+m(X\cap
Y)=m(X)+m(Y)=p(X)+p(Y).$

Here, the second inequality is because $m(Z)\geq p(Z)$ for every $Z\subseteq
V$. The final equality is because the sets $X,Y\in T_{p,m}$. Thus, we have
that all inequalities are equations. In particular, the second inequality is
an equation and consequently the set $p(X\cup Y)=m(X\cup Y)$ and $p(X\cap
Y)=m(X\cap Y)$.

  2. (b)

By way of contradiction, let $X,Y\in\calT_{p,m}$ be distinct maximal tight
sets such that $X\cap Y\not=\emptyset$. We note that since the sets $X,Y$ are
distinct and maximal, $X-Y,Y-X\not=\emptyset$. Since $X,Y\in T_{p,m}$, by part
(a) of the current lemma (shown above), we have that $X\cup Y\in T_{p,m}$,
contradicting maximality of the sets $X,Y\in\calT_{p,m}$.

  3. (c)

Let $X\cap Y\not=\emptyset$ and suppose by way of contradiction that
$X-Y\not=\emptyset$. We consider two cases based on the behavior of the
function $p$ at the sets $X,Y$ and arrive at a contradiction in both cases.
First, suppose that $p(X)+p(Y)\leq p(X\cup Y)+p(X\cap Y)$. Then, we have that

$p(X)+p(Y)\leq p(X\cup Y)+p(X\cap Y)\leq p(Y)+m(X\cap Y)<p(Y)+m(X)=p(Y)+p(X),$

which is a contradiction. Here, the second inequality is because the set
$Y\in\calF_{p}$ is a $p$-maximizer and $m(Z)\geq p(Z)$ for every $Z\subseteq
V$. The third inequality is because the function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function and $X-Y\not=\emptyset$.
The final equality is because $X\in\calT_{p,m}$. Next, suppose that
$p(X)+p(Y)\leq p(X-Y)+p(Y-X)$. Then, we have that:

$p(X)+p(Y)\leq p(X-Y)+p(Y-X)<m(X-Y)+p(Y)<m(X)+p(Y)=p(X)+p(Y),$

which is a contradiction. Here, the second inequality is because the set
$Y\in\calF_{p}$ is a $p$-maximizer and $m(Z)\geq p(Z)$ for every $Z\subseteq
V$. The third inequality is the function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function and $X-Y\not=\emptyset$.
The final equality is because $X\in\calT_{p,m}$.

∎

In the remainder of the section, we will examine the progression of the
maximal $(p,m)$-tight set family across an execution of Algorithm 2. Consider
an execution of Algorithm 2 with $\ell\in\Z_{+}$ recursive calls. Suppose that
the input to the $i^{th}$ recursive call is the tuple $(p_{i},m_{i},J_{i})$.
For every $i\in[\ell-1]$, we let $T_{i},T_{i}^{\prime},\calT_{i}$, and
$\calT_{i}^{\prime}$ denote the families
$T_{p_{i},m_{i}},T_{p_{i}^{\prime},m_{i}^{\prime}},\calT_{p_{i},m_{i}}$, and
$\calT_{p_{i}^{\prime},m_{i}^{\prime}}$ respectively. For convenience, we also
define the families $T_{\ell},T_{\ell}^{\prime}\coloneqq
T_{p_{\ell},m_{\ell}}$ and
$\calT_{\ell},\calT_{\ell}^{\prime},\coloneqq\calT_{p_{\ell},m_{\ell}}$.
Furthermore, we define the family of _cumulative projected maximal
$(p_{i},m_{i})$-tight sets_ as

$\displaystyle\calT_{\leq i}$
$\displaystyle\coloneqq\begin{cases}\calT_{1}&\text{if $i=1$,}\\\ \calT_{\leq
i-1}|_{V_{i}}\cup\calT_{i}&\text{otherwise.}\end{cases}$ $\forall i\in[\ell]$.

In the next lemma, we prove several useful properties of these set families
during feasible executions of Algorithm 2.

######  Lemma 5.19.

Consider a feasible execution of Algorithm 2 on an input instance that
terminates in $\ell\in\Z_{+}$ recursive calls. For every $i\in[\ell]$, suppose
that the input to the $i^{th}$ recursive call of Algorithm 2 is a tuple
$(p_{i},m_{i},J_{i})$, where $p_{1}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is a skew-supermodular function with
$K_{p_{1}}>0$, $m_{1}\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$
is a positive function, and $J_{1}\subseteq V$ is an arbitrary set such that
$m_{1}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and $m_{1}(u)\leq K_{p_{1}}$
for every $u\in V$. Then, for every $i\in[\ell-1]$ we have that

  1. (a)

$T_{i}\subseteq T_{i}^{\prime}$,

  2. (b)

$T_{i}^{\prime}|_{V_{i+1}}\subseteq T_{i+1}$,

  3. (c)

$\calT_{\leq i}\subseteq T_{i}$,

  4. (d)

the family $\calT_{\leq i}$ is laminar, and

  5. (e)

if $\mathcal{Z}_{i}=\emptyset$ and $\calT_{\leq i}=\calT_{\leq i+1}$, then
$\calT_{i}=\calT_{i+1}$.

###### Proof.

Let $i\in[\ell-1]$ be a recursive call. By Corollary 5.3 and induction on $i$,
we have that $p_{i}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{i}}\rightarrow\Z$ is skew-supermodular function with
$K_{p_{i}}>0$, $m_{i}\mathrel{\mathop{\mathchar
58\relax}}V_{i}\rightarrow\Z_{+}$ is a positive function such that
$m_{i}(X)\geq p_{i}(X)$ for every $X\subseteq V_{i}$, $m_{i}(u)\leq K_{p_{i}}$
for every $u\in V_{i}$ and $Q(p_{i},m_{i})$ is a non-empty integral
polyhedron. We now prove each claim separately below.

  1. (a)

Let $X\in T_{i}$. We first show that $|A_{i}\cap X|\leq 1$. By way of
contradiction, let $|A_{i}\cap X|\geq 2$. Then, we have the following:

$\displaystyle m_{i}^{\prime}(X)$
$\displaystyle=m_{i}(X)-\alpha_{i}\chi_{A_{i}}(X)$
$\displaystyle=p_{i}(X)-\alpha_{i}\chi_{A_{i}}(X)$ $\displaystyle\leq
p_{i}(X)-2\alpha_{i}$
$\displaystyle<p_{i}(X)-\alpha_{i}b_{(V_{i},\\{A_{i}\\})}(X)$
$\displaystyle=p_{i}^{\prime}(X),$

which is a contradiction to the functions $m_{i}^{\prime}(X)\geq
p_{i}^{\prime}(X)$ by Lemma 5.3(d). Here, the second equality is because $X\in
T_{i}$, the first inequality is by our assumption that $|A_{i}\cap X|\geq 2$
and the second inequality is because $b_{(V_{i},\\{A_{i}\\})}(X)=1$. We now
show that $X\in T_{i}^{\prime}$. We have the following:

$m_{i}^{\prime}(X)=m_{i}(X)-\alpha_{i}|A_{i}\cap
X|=p_{i}(X)-\alpha_{i}b_{(V_{i},\\{A_{i}\\})}(X)=p_{i}^{\prime}(X).$

Here, the second equality holds because $X\in T_{i}$, and
$b_{(V_{i},\\{A_{i}\\})}(X)=|A_{i}\cap X|$ since $|A_{i}\cap X|\leq 1$.

  2. (b)

We note that each set in the family $T_{i}^{\prime}|_{V_{i+1}}$ is of the form
$Y-\mathcal{Z}_{i}$ for some set $Y\in T_{i}^{\prime}$. Thus, it suffices to
consider an arbitrary set $X\in T_{i}^{\prime}$ and show that
$X-\mathcal{Z}_{i}\in T_{i+1}$. We have the following:

$m_{i+1}(X-\mathcal{Z}_{i})=m_{i}^{\prime}(X)=p_{i}^{\prime}(X)\leq
p_{i+1}(X-\mathcal{Z}_{i})\leq m_{i+1}(X-\mathcal{Z}_{i}).$

Thus, all inequalities are equations and we have that $X-\mathcal{Z}\in
T_{i+1}$. Here, the first equality is because $m^{\prime}(\mathcal{Z}_{i})=0$.
The second equality is because $X\in T_{i}^{\prime}$. The first inequality is
because $p_{i+1}={p_{i}^{\prime}}/_{\mathcal{Z}_{i}}$. The final inequality is
because the functions $m_{i+1}$ and $p_{i+1}$ satisfy condition
$m_{i+1}(Z)\geq p_{i+1}(Z)$ for every $Z\subseteq V_{i+1}$. We remark that the
statement (and proof) of this part can be strengthened to say that
$T_{i}^{\prime}|_{V_{i+1}}=T_{i+1}$, but the weaker statement suffices for our
purposes and so we omit the details.

  3. (c)

By way of contradiction, let $i\in[\ell-1]$ be the smallest recursive call
such that the claim is false. We note that $i\geq 2$ because $\calT_{\leq
1}=\calT_{1}\subseteq T_{1}$. Thus, we have that $\calT_{\leq i}=\calT_{\leq
i-1}|_{V_{i}}\cup\calT_{i}$. We observe that $\calT_{\leq i-1}\subseteq
T_{i-1}\subseteq T_{i-1}^{\prime}$, where the first inclusion is by our choice
of $i\in[\ell-1]$, and the second inclusion is by part (1) of the current
lemma (shown above). Furthermore, we have that $\calT_{\leq
i-1}|_{V_{i}}\subseteq T_{i-1}^{\prime}|_{V_{i}}\subseteq T_{i}$ , where the
second inclusion is by part (2) of the current lemma (shown above). Thus,
$\calT_{\leq i}\subseteq T_{i}$.

  4. (d)

By way of contradiction, let $i\in[\ell-1]$ be the smallest recursive call
such that the family $\calT_{\leq i}$ is not laminar. We note that $i\geq 2$
since the family $\calT_{\leq 1}=\calT_{1}$ is disjoint by Lemma 5.18(b).
Thus, we have that $\calT_{\leq i}=\calT_{\leq i-1}|_{V_{i}}\cup\calT_{i}$. We
note that the family $\calT_{i}$ is also disjoint by Lemma 5.18(b).
Furthermore, the family $\calT_{\leq i-1}$ is laminar by our choice of
$i\in[\ell-1]$. Since the family $\calT_{\leq i}$ is not laminar, there exist
distinct sets $X\in\calT_{\leq i-1}|_{V_{i}}$ and $Y\in\calT_{i}$ such that
$X-Y,Y-X,X\cap Y\not=\emptyset$. By part (c) of the current lemma (shown
above), we have that $X\in T_{i}$. Consequently, there exists $Z\in\calT_{i}$
such that $X\subseteq Z$. We note that $Y\not=Z$ because $X-Z=\emptyset$ and
$X-Y\not=\emptyset$. Thus, by Lemma 5.18(b) we have that $Z\cap Y=\emptyset$.
Therefore, $X\cap Y=\emptyset$, contradicting our choice of sets $X$ and $Y$.

  5. (e)

We first show that $\calT_{i+1}\subseteq\calT_{i}$. By way of contradiction,
let $X\in\calT_{i+1}-\calT_{i}\not=\emptyset$. We note that since
$\calT_{i+1}\subseteq\calT_{\leq i+1}=\calT_{\leq i}$, the set
$X\in\calT_{\leq i}$. Furthermore, since $X\not\in\calT_{i}$, we have that
$X\in\calT_{\leq i-1}|_{V_{i}}$ by definition of the family $\calT_{\leq i}$.
By part (c) of the current lemma (shown above) and
$\mathcal{Z}_{i}=\emptyset$, we have that $X\in T_{i}$. Thus, there exists a
$Y\in\calT_{i}$ such that $X\subsetneq Y$, where the inclusion is strict
because $X\not\in\calT_{i}$. By parts (a) and (b) of the current lemma (shown
above), we have that $Y\in T_{i+1}$, contradicting maximality of
$X\in\calT_{i+1}$.

Next, we show that $\calT_{i}\subseteq\calT_{i+1}$. By way of contradiction,
let $X\in\calT_{i}-\calT_{i+1}\not=\emptyset$. By parts (a) and (b) of the
current lemma (shown above) and $\mathcal{Z}_{i}=\emptyset$, we have that
$X\in T_{i+1}$. Thus, there exists $Y\in\calT_{i+1}$ such that $X\subsetneq
Y$, where the strict inclusion is because $X\not\in\calT_{i+1}$. By the
previous paragraph, we have that $\calT_{i+1}\subseteq\calT_{i}$. Consequently
$Y\in\calT_{i}$, contradicting maximality of the set $X\in\calT_{i}$.

∎

####  5.6.2 Adding Good Hyperedges

In this section, we show an important property of the set $A$ chosen during a
recursive call of Algorithm 2. This property will be useful to bound the
number of recursive calls of the algorithm and the number of hyperedges
returned by the algorithm. We now formally define the property.

######  Definition 5.2 ($\alpha\text{-good}$ Sets).

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ and
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z$ be functions defined
over a finite set $V$ and $\alpha$ be a non-negative real value. A set
$A\subseteq V$ is _$\alpha$ -good for a set $Z\subseteq V$ w.r.t. the
functions $p$ and $m$_ if the following three properties hold:

$\displaystyle(1)\ $ $\chi_{A}\in Q(p,m)$, $\displaystyle(2)\ $ $\alpha|A\cap
Z|=m(Z)-p(Z)+\alpha$, and ($\alpha$-Good-Set) $\displaystyle(3)\ $ there is no
$Y\in\calT_{p,m}$ such that $Z\subseteq Y$.

Furthermore, the set $A\subseteq V$ is _$\alpha$ -good w.r.t the functions $p$
and $m$_ if there exists a set $Z\subseteq V$ such that $A$ is $\alpha$-good
for the set $Z$ w.r.t functions $p$ and $m$.

Before showing the main lemma of the section, we show the following lemma
which highlights the use of $\alpha\text{-good}$ sets. It shows that during a
feasible recursive call where the set $A$ chosen by the algorithm is
$\alpha\text{-good}$ for a set $Z\subseteq V$, some superset of $Z$ is added
to the maximal tight set family (prior to function contractions).

######  Lemma 5.20.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a skew-
supermodular function with $K_{p}>0$, $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function, and $J\subseteq V$ is an
arbitrary set such that $m(X)\geq p(X)$ for every $X\subseteq V$, $m(u)\leq
K_{p}$ for every $u\in V$ and $Q(p,m)$ is an integral polyhedron. Let
$A,\alpha,p^{\prime},m^{\prime}$ be as defined by Algorithm 2. Suppose that
the set $A$ is $\alpha\text{-good}$ w.r.t. the functions $p$ and $m$. Then, we
have that $\calT_{p^{\prime},m^{\prime}}-\calT_{p,m}\not=\emptyset$.

###### Proof.

Let $Z\subseteq V$ be such that the set $A$ is $\alpha\text{-good}$ for the
set $Z$ w.r.t. the functions $p$ and $m$. We first show that $|A\cap Z|\geq
2$. We note that by ($\alpha$-Good-Set) property (3), the set $Z$ is not a
tight set for the functions $p$ and $m$, i.e. $m(Z)>p(Z)$. Thus, we have that
$|A\cap Z|=\frac{1}{\alpha}\left(m(Z)-p(Z)+\alpha\right)>1,$ where the
equality is by ($\alpha$-Good-Set) property (2) and Lemma 5.2(1) – we note
that $\chi_{A}\in Q_{p,m}\not=\emptyset$ by ($\alpha$-Good-Set) property (1).

Then, the following sequence of equations shows that the set $Z$ is a tight
set for the functions $p^{\prime}$ and $m^{\prime}$. This implies the
existence of a maximal tight set $Y\in\calT_{p^{\prime},m^{\prime}}$ such that
$Z\subseteq Y$ and the claim follows as a consequence of ($\alpha$-Good-Set)
property (3).

$p^{\prime}(Z)=p(Z)-\alpha b_{(V,\\{A\\})}(Z)=p(Z)-\alpha=m(Z)-\alpha|A\cap
Z|=m^{\prime}(Z).$

Here, the second equality is because $|A\cap Z|\geq 1$. The third equality is
due to ($\alpha$-Good-Set) property (2). ∎

The following is the main lemma of this section. It shows that if a recursive
call of Algorithm 2 witnesses
$\alpha=\alpha^{(4)}<\min\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$,
then at least one of the following happens: (1)
$\calF_{p^{\prime\prime}}-\calF_{p}\neq\emptyset$, (2)
$\calT_{p^{\prime\prime},m^{\prime\prime}}-\calT_{p,m}\neq\emptyset$, and (3)
the hyperedge selected by the algorithm in the subsequent recursive call is
$1$-good w.r.t. the functions $p^{\prime\prime}$ and $m^{\prime\prime}$.

######  Lemma 5.21.

Suppose that the input to Algorithm 2 is a tuple $(p,m,J)$, where
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is a skew-
supermodular function with $K_{p}>0$, $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a positive function, and $J\subseteq V$ is an
arbitrary set such that $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq
K_{p}$ for every $u\in V$. Let
$A,\alpha,\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(4)},\alpha^{(5)},p^{\prime},m^{\prime}$,
$p^{\prime\prime},m^{\prime\prime}$ be as defined by Algorithm 2. Suppose that
$\alpha=\alpha^{(4)}<\min\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$
and $K_{p^{\prime\prime}}>0$. Then, at least one of the following properties
hold:

  1. (1)

$\calF_{p^{\prime\prime}}-\calF_{p}\not=\emptyset$,

  2. (2)

$\calT_{p^{\prime\prime},m^{\prime\prime}}-\calT_{p,m}\not=\emptyset$, and

  3. (3)

let $y$ be an extreme point optimum solution to $\max\left\\{\sum_{u\in
A}y_{u}\mathrel{\mathop{\mathchar 58\relax}}y\in