problem[1]

#1

# Hypergraph Connectivity Augmentation
in Strongly Polynomial Time

Kristóf Bérczi MTA-ELTE Matroid Optimization Research Group and HUN-REN-ELTE
Egerváry Research Group, Department of Operations Research, ELTE Eötvös Loránd
University, Budapest, Hungary, Email: {kristof.berczi,
<EMAIL_ADDRESS>Karthekeyan Chandrasekaran University of Illinois,
Urbana-Champaign, USA, Email: {karthe<EMAIL_ADDRESS>Part of this
work was done while Karthekeyan and Shubhang were visiting Eötvös Loránd
University. Tamás Király11footnotemark: 1 Shubhang Kulkarni22footnotemark: 2

###### Abstract

We consider hypergraph network design problems where the goal is to construct
a hypergraph that satisfies certain connectivity requirements. For graph
network design problems where the goal is to construct a graph that satisfies
certain connectivity requirements, the number of edges in every feasible
solution is at most quadratic in the number of vertices. In contrast, for
hypergraph network design problems, we might have feasible solutions in which
the number of hyperedges is exponential in the number of vertices. This
presents an additional technical challenge in hypergraph network design
problems compared to graph network design problems: in order to solve the
problem in polynomial time, we first need to show that there exists a feasible
solution in which the number of hyperedges is polynomial in the input size.

The central theme of this work is to show that certain hypergraph network
design problems admit solutions in which the number of hyperedges is
polynomial in the number of vertices and moreover, can be solved in strongly
polynomial time. Our work improves on the previous fastest pseudo-polynomial
run-time for these problems. In addition, we develop strongly polynomial time
algorithms that return near-uniform hypergraphs as solutions (i.e., every pair
of hyperedges differ in size by at most one). As applications of our results,
we derive the first strongly polynomial time algorithms for (i) degree-
specified hypergraph connectivity augmentation using hyperedges, (ii) degree-
specified hypergraph node-to-area connectivity augmentation using hyperedges,
and (iii) degree-constrained mixed-hypergraph connectivity augmentation using
hyperedges.

###### Contents

  1. 1 Introduction
    1. 1.1 Degree-specified skew-supermodular cover problems
    2. 1.2 Results
    3. 1.3 Techniques: Structural and Algorithmic Results
      1. 1.3.1 Proof Technique for Theorem 1.7
      2. 1.3.2 Proof Technique for Theorems 1.8 and 1.9
    4. 1.4 Related Work
  2. 2 Preliminaries
  3. 3 Minimal Maximizers of Skew-Supermodular Function Sequences
  4. 4 Weak Cover with Linear Number of Hyperedges
    1. 4.1 The Algorithm
    2. 4.2 Termination and Partial Correctness
    3. 4.3 Recursion Depth and Hypergraph Support Size
    4. 4.4 Runtime
  5. 5 Weak Cover using Near-Uniform Hyperedges
    1. 5.1 The Algorithm
    2. 5.2 Termination and Partial Correctness of Algorithm 2
    3. 5.3 Number of Recursive Calls of Algorithm 2 with $\alpha\in\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$
    4. 5.4 Feasibility of Execution for Skew-supermodular Functions
    5. 5.5 Run-time for Skew-supermodular Functions
    6. 5.6 Weak Cover of One Function with Linear Number of Near-Uniform Hyperedges
      1. 5.6.1 Laminarity of Projected Maximal Tight Sets Across Recursive Calls
      2. 5.6.2 Adding Good Hyperedges
      3. 5.6.3 Number of Recursive Calls and Hypergraph Support Size
    7. 5.7 Weak Cover of Two Functions with Quadratic Number of Near-Uniform Hyperedges
      1. 5.7.1 Slack and Pairwise Slack Functions
      2. 5.7.2 Number of Recursive Calls and Hypergraph Support Size
  6. 6 Applications
    1. 6.1 Strong cover to weak cover reduction for symmetric skew-supermodular functions
    2. 6.2 Hypergraph local connectivity augmentation using hyperedges
    3. 6.3 Hypergraph node-to-area connectivity augmentation using hyperedges
    4. 6.4 Degree-constrained mixed-hypergraph global connectivity augmentation using hyperedges
  7. 7 Conclusion
  8. A Maximization oracles for functions arising in applications
  9. B Properties of Laminar Families and Skew-Supermodular Functions
    1. B.1 Cumulative Minimal Maximizer Family Across Function Sequences
    2. B.2 Optimizing over $Q$-polyhedron in Strongly Polynomial Time
    3. B.3 Computing $\alpha^{(4)}$: Ratio Maximization Oracle in Strongly Polynomial Time

##  1 Introduction

In the degree-specified graph connectivity augmentation using edges problem
(DS-Graph-CA-using-E), we are given an edge-weighted undirected graph
$(G=(V,E_{G}),c_{G}\mathrel{\mathop{\mathchar
58\relax}}E_{G}\rightarrow\Z_{+})$, a degree-requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$, and a target
connectivity function $r\mathrel{\mathop{\mathchar
58\relax}}\binom{V}{2}\rightarrow\Z_{\geq 0}$. The goal is to verify if there
exists an edge-weighted undirected graph
$(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ such that the degree of each vertex $u$ in
$(H,w_{H})$ is $m(u)$ and for every distinct pair of vertices $u,v\in V$, the
edge connectivity between $u$ and $v$ in the union of the weighted graphs
$(G,c_{G})$ and $(H,w_{H})$ is at least $r(u,v)$; moreover, the problem asks
to construct such a graph $(H,w_{H})$ if it exists. Watanabe and Nakamura [65]
introduced DS-Graph-CA-using-E for the case of uniform requirement function
(i.e., $r(u,v)=k$ for all distinct $u,v\in V$ for some $k\in\Z_{+}$) and
showed that this case is solvable in polynomial time in unweighted graphs.
Subsequently, Frank [28] gave a strongly polynomial-time algorithm for DS-
Graph-CA-using-E. Since then, designing fast algorithms as well as parallel
algorithms for DS-Graph-CA-using-E has been an active area of research [12,
29, 5, 32, 10, 49, 6, 44]. The last couple of years has seen exciting progress
for the uniform requirement function culminating in a near-linear time
algorithm [14, 15, 13]. In addition to making progress in the algorithmic
status of the problem, these works have revealed fundamental structural
properties of graph cuts which are of independent interest in graph theory. In
this work, we consider generalizations of these connectivity augmentation
problems to hypergraphs and design the first strongly polynomial-time
algorithms for these generalizations.

We emphasize that DS-Graph-CA-using-E is a feasibility problem, i.e., the goal
is to verify if there exists a feasible solution and if so, then find one.
There is a closely related optimization variant: the input to the optimization
version is a graph $(G=(V,E_{G}),c_{G}\mathrel{\mathop{\mathchar
58\relax}}E_{G}\rightarrow\Z_{+})$ and a target connectivity function
$r\mathrel{\mathop{\mathchar 58\relax}}\binom{V}{2}\rightarrow\Z_{+}$ and the
goal is to find a graph $(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ with minimum total weight $\sum_{e\in
E_{H}}w_{H}(e)$ such that for every pair of distinct vertices $u,v\in V$, the
edge connectivity between $u$ and $v$ in the union of the weighted graphs
$(G,c_{G})$ and $(H,w_{H})$ is at least $r(u,v)$. This optimization version is
different from the NP-hard min-cost connectivity augmentation problems (like
Steiner tree and tree/cactus/forest augmentation) whose approximability have
been improved recently [59, 11, 61, 35, 60]. All algorithms to solve the
optimization version [65, 12, 28, 29, 32, 10, 49, 5, 6, 44] reduce it to
solving the degree-specified feasibility version, i.e., DS-Graph-CA-using-E,
so we focus only on the degree-specified feasibility variant and their
generalization to hypergraphs throughout this work. All our results can be
extended to an optimization variant, but we avoid stating them in the
interests of brevity.

##### Hypergraphs.

Edges are helpful to model relationships between pairs of entities. Hyperedges
are helpful to model relationships between arbitrary number of entities. For
this reason, hypergraphs are more accurate models for a rich variety of
applications in bioinformatics, statistical physics, and machine learning
(e.g., see [63, 53, 46, 51, 25, 66, 42, 24, 26, 64]). These applications have
in turn, renewed interests in algorithms for hypergraph optimization problems
[43, 34, 18, 19, 16, 20, 57, 2, 41, 40, 45, 39, 52, 36, 4, 3, 17, 1, 27]. A
hypergraph $G=(V,E)$ consists of a finite set $V$ of vertices and a set $E$ of
hyperedges, where every hyperedge $e\in E$ is a subset of $V$. Equivalently, a
hypergraph is a set system defined over a finite set. We will denote a
hypergraph $G=(V,E)$ with hyperedge weights $w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}$ by the tuple $(G,w)$. Throughout this work, we
will be interested only in hypergraphs with positive integral weights and for
algorithmic problems where the input/output is a hypergraph, we will require
that the weights are represented in binary. If all hyperedges have size at
most $2$, then the hyperedges are known as edges and we call such a hypergraph
as a graph.

We emphasize a subtle but important distinction between hypergraphs and
graphs: the number of hyperedges in a hypergraph could be exponential in the
number of vertices. This is in sharp contrast to graphs where the number of
edges is at most the square of the number of vertices. Consequently, in
hypergraph network design problems where the goal is to construct a hypergraph
with certain properties, we have to be mindful of the number of hyperedges in
the solution hypergraph (to be returned by the algorithm). This nuanced issue
adds an extra challenging layer to hypergraph network design compared to graph
network design problems – e.g., membership in NP becomes non-trivial. Recent
works in hypergraph algorithms literature have focused on the number of
hyperedges in the context of cut/spectral sparsification of hypergraphs [43,
19, 57, 2, 20, 41, 40, 45, 39, 52]. We will return to the membership in NP
issue after we define the relevant problems of interest to this work.

##### Notation.

Let $(G=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ be a
hypergraph. For $X\subseteq V$, let $\delta_{G}(X)\coloneqq\\{e\in
E\mathrel{\mathop{\mathchar 58\relax}}e\cap X\neq\emptyset,e\setminus
X\neq\emptyset\\}$ and $B_{G}(X)\coloneqq\\{e\in E\mathrel{\mathop{\mathchar
58\relax}}e\cap X\neq\emptyset\\}$. We define the cut function
$d_{(G,w)}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z_{\geq 0}$ by
$d_{(G,w)}(X)\coloneqq\sum_{e\in\delta_{G}(X)}w(e)$ for every $X\subseteq V$
and the coverage function $b_{(G,w)}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z_{\geq 0}$ by $b_{(G,w)}(X)\coloneqq\sum_{e\in
B_{G}(X)}w(e)$ for every $X\subseteq V$. For a vertex $v\in V$, we use
$d_{(G,w)}(v)$ and $b_{(G,w)}(v)$ to denote $d_{(G,w)}(\\{v\\})$ and
$b_{(G,w)}(\\{v\\})$ respectively. We define the _degree_ of a vertex $v$ to
be $b_{(G,w)}(v)$ – we note that the degree of a vertex is not necessarily
equal to $d_{(G,w)}(v)$ since we could have $\\{v\\}$ itself as a hyperedge
(i.e., a singleton hyperedge that contains only the vertex $v$). For distinct
vertices $u,v\in V$, the connectivity between $u$ and $v$ in $(G,w)$ is
$\lambda_{(G,w)}(u,v)\coloneqq\min\\{d_{(G,w)}(X)\mathrel{\mathop{\mathchar
58\relax}}u\in X\subseteq V\setminus\\{v\\}\\}$ – i.e., $\lambda_{(G,w)}(u,v)$
is the value of a minimum $\\{u,v\\}$-cut in the hypergraph. For two
hypergraphs $(G=(V,E_{G}),c_{G}\mathrel{\mathop{\mathchar
58\relax}}E_{G}\rightarrow\Z_{+})$ and
$(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ on the same vertex set $V$, we define the
hypergraph $(G+H=(V,E_{G+H}),c_{G}+w_{H})$ as the hypergraph with vertex set
$V$ and hyperedge set $E_{G+H}\coloneqq E_{G}\cup E_{H}$ with the weight of
every hyperedge $e\in E_{G}\cap E_{H}$ being $c_{G}(e)+w_{H}(e)$, the weight
of every hyperedge $e\in E_{G}\setminus E_{H}$ being $c_{G}(e)$, and the
weight of every hyperedge $e\in E_{H}\setminus E_{G}$ being $w_{H}(e)$.

##### Degree-Specified Hypergraph Connectivity Augmentation.

We define the degree-specified hypergraph connectivity augmentation using
hyperedges problem below.

Degree-specified Hypergraph Connectivity Augmentation using Hyperedges
(DS-Hypergraph-CA-using-H). Given: A hypergraph
$(G=(V,E_{G},c_{G}\mathrel{\mathop{\mathchar
58\relax}}E_{G}\rightarrow\Z_{+})$,
target connectivity function $r\mathrel{\mathop{\mathchar
58\relax}}\binom{V}{2}\rightarrow\Z_{\geq 0}$, and
degree requirement function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$. Goal: Verify if there exists a hypergraph
$(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ such that
$b_{(H,w_{H})}(u)=m(u)$ for every $u\in V$ and
$\lambda_{(G+H,c_{G}+w_{H})}(u,v)\geq r(u,v)$ for every distinct $u,v\in V$,
and if so, then find such a hypergraph.

We remark on certain aspects of the problem to illustrate the challenges.

######  Remark 1.1.

There is a fundamental distinction between DS-Hypergraph-CA-using-H and DS-
Graph-CA-using-E: it is clear that DS-Graph-CA-using-E is in NP since YES
instances admit a weighted _graph_ $(H,w_{H})$ as a feasible solution which
serves as a polynomial-time verifiable certificate of YES instances; in
contrast, it is not immediately clear if DS-Hypergraph-CA-using-H is in NP.
This is because, the number of hyperedges in the desired hypergraph
$(H,w_{H})$ could be exponential in the number of vertices, and consequently,
exponential in the size of the input. We give an example to illustrate this
issue: suppose that the input instance is given by the empty hypergraph
$(G,c_{G})$ on $n$ vertices, the target connectivity function $r$ is given by
$r(u,v)\mathrel{\mathop{\mathchar 58\relax}}=2^{n-1}-1$ for every pair of
distinct vertices $u,v\in V$ and the degree requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ is given by
$m(u)\mathrel{\mathop{\mathchar 58\relax}}=2^{n-1}$ for every vertex $u\in V$.
We note that the input specification needs only $n^{O(1)}$ bits. Consider the
hypergraph $(H=(V,E_{H}),w_{H})$ where $E_{H}\mathrel{\mathop{\mathchar
58\relax}}=\\{e\subseteq V\mathrel{\mathop{\mathchar 58\relax}}|e|\geq 2\\}$
with all hyperedge weights being one. The hypergraph $(H,w_{H})$ is a feasible
solution to the input instance but the number of hyperedges in this hypergraph
is $2^{n}-n-1$ which is exponential in the number of vertices (and hence, the
input size). Thus, in order to design a polynomial-time algorithm for DS-
Hypergraph-CA-using-H, a necessary first step is to exhibit the existence of a
feasible solution in which the number of hyperedges is polynomial in the input
size, i.e., prove membership in NP. For the input instance mentioned here,
there is indeed a feasible solution with one hyperedge: the hypergraph
$(H^{\prime}=(V,E_{H^{\prime}}),w_{H^{\prime}})$ containing only one
hyperedge, namely $E_{H^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}=\\{V\\}$ with the weight of that hyperedge being $2^{n-1}-1$.

######  Remark 1.2.

Given that membership in NP is non-trivial, it is tempting to constrain the
target hypergraph $(H,w_{H})$ to be a graph. This leads to the degree-
specified hypergraph connectivity augmentation using edges problem (DS-
Hypergraph-CA-using-E): here, we have the same input as DS-Hypergraph-CA-
using-H; the goal is to verify if there exists a _graph_
$(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$
with the same properties as above and if so, then find one. Clearly, DS-
Hypergraph-CA-using-E is in NP since YES instances admit a weighted _graph_
$(H,w_{H})$ as a feasible solution which serves as a polynomial-time
verifiable certificate of YES instances. However, DS-Hypergraph-CA-using-E is
NP-complete [22, 47] (see Table 1).

Showing the existence of a feasible solution hypergraph with small number of
hyperedges is a technical challenge in hypergraph network design problems.
During first read, we encourage the reader to focus on this issue for all
problems that we define and how it is addressed by our results and techniques.
The algorithmic results that we present are consequences of our techniques to
address this issue (using standard algorithmic tools in submodularity).

We now discuss the status of DS-Hypergraph-CA-using-H. Szigeti [58] showed
that DS-Hypergraph-CA-using-H can be solved in pseudo-polynomial time: in
particular, if the target connectivity function $r\mathrel{\mathop{\mathchar
58\relax}}\binom{V}{2}\rightarrow\Z_{\geq 0}$ is given in unary, then the
problem can be solved in polynomial time. Moreover, his result implies that if
the input instance is feasible, then it admits a solution hypergraph
$(H,w_{H})$ such that the number of hyperedges in $H$ is at most
$\max\\{2^{|V|},\max\\{r(u,v)\mathrel{\mathop{\mathchar
58\relax}}\\{u,v\\}\in\binom{V}{2}\\}\\}$. In this work, we show that feasible
instances admit a solution with $O(|V|)$ hyperedges and give a strongly
polynomial time algorithm.

######  Theorem 1.1.

There exists an algorithm to solve DS-Hypergraph-CA-using-H that runs in time
$O(n^{7}(n+m)^{2})$, where $n$ is the number of vertices and $m$ is the number
of hypergedges in the input hypergraph. Moreover, if the instance is feasible,
then the algorithm returns a solution hypergraph that contains $O(n)$
hyperedges.

Next, we consider a constrained-variant of DS-Hypergraph-CA-using-H. A
hypergraph is _uniform_ if all hyperedges have the same size; a hypergraph is
_near-uniform_ if every pair of hyperedges differ in size by at most one. We
note that every graph is a near-uniform hypergraph. Uniformity/near-uniformity
is a natural constraint in network design applications involving hypergraphs –
we might be able to create only equal-sized hyperedges in certain
applications. Requiring uniform (or near-uniform) hyperedges can also be
viewed as a fairness inducing constraint in certain applications. Bernáth and
Király [8] showed that if an instance of DS-Hypergraph-CA-using-H is feasible,
then it admits a near-uniform hypergraph as a solution. Moreover, their proof
technique implies a pseudo-polynomial time algorithm to return a solution
hypergraph that is near-uniform for feasible instances. In this work, we show
that feasible instances admit a solution with $O(|V|)$ near-uniform hyperedges
and give a strongly polynomial time algorithm.

######  Theorem 1.2.

There exists a strongly polynomial time algorithm to solve DS-Hypergraph-CA-
using-H. Moreover, if the instance is feasible, then the algorithm returns a
solution hypergraph that is near-uniform and contains $O(n)$ hyperedges, where
$n$ is the number of vertices in the input hypergraph.

Next, we consider a variant of hypergraph connectivity augmentation where the
goal is to simultaneously augment two input hypergraphs to achieve certain
target connectivities using the same degree-specified hypergraph.

Degree-specified Simultaneous Hypergraph Connectivity Augmentation Hyperedges
(DS-Simul-Hypergraph-CA-using-H). Given: Hypergraphs
$(G_{i}=(V,E_{i}),c_{i}\mathrel{\mathop{\mathchar
58\relax}}E_{i}\rightarrow\Z_{+})$ for $i\in\\{1,2\\}$,
target connectivity functions $r_{i}\mathrel{\mathop{\mathchar
58\relax}}\binom{V}{2}\rightarrow\Z_{\geq 0}$ for $i\in\\{1,2\\}$ such that
$\max\\{r_{1}(u,v)-\lambda_{(G_{1},c_{1})}(u,v)\mathrel{\mathop{\mathchar
58\relax}}u,v\in
V\\}=\max\\{r_{2}(u,v)-\lambda_{(G_{2},c_{2})}(u,v)\mathrel{\mathop{\mathchar
58\relax}}u,v\in V\\}$, and
degree requirement function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$. Goal: Verify if there exists a hypergraph
$(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ such that
$b_{(H,w_{H})}(u)=m(u)$ for every $u\in V$ and
$\lambda_{(G_{i}+H,c_{i}+w_{H})}(u,v)\geq r_{i}(u,v)$ for every distinct
$u,v\in V$ and $i\in\\{1,2\\}$,
and if so, then find such a hypergraph.

Bernáth and Király [8] proposed the above problem and showed that if the
assumption
$\max\\{r_{1}(u,v)-\lambda_{(G_{1},c_{1})}(u,v)\mathrel{\mathop{\mathchar
58\relax}}u,v\in
V\\}=\max\\{r_{2}(u,v)-\lambda_{(G_{2},c_{2})}(u,v)\mathrel{\mathop{\mathchar
58\relax}}u,v\in V\\}$ does not hold, then the problem is NP-complete. So, we
include this assumption in the definition of the problem statement. In the
same work, they gave a pseudo-polynomial time algorithm for DS-Simul-
Hypergraph-CA-using-H; moreover, they showed that if an instance of DS-Simul-
Hypergraph-CA-using-H is feasible, then it admits a near-uniform hypergraph as
a solution. In this work, we show that feasible instances of DS-Simul-
Hypergraph-CA-using-H admit a solution with $O(|V|^{2})$ near-uniform
hyperedges and give a strongly polynomial time algorithm.

######  Theorem 1.3.

There exists a strongly polynomial time algorithm to solve DS-Simul-
Hypergraph-CA-using-H. Moreover, if the instance is feasible, then the
algorithm returns a solution hypergraph that is near-uniform and contains
$O(n^{2})$ hyperedges, where $n$ is the number of vertices in the input
hypergraph.

Our algorithm for Theorems 1.2 and 1.3 are LP-based. The associated LPs can be
solved in strongly polynomial time. However, the LP-solving time is large, so
we refrain from stating the run-times explicitly. In contrast, our algorithm
for Theorem 1.1 is combinatorial and hence, we are able to provide an explicit
bound on the run-time. We refer the reader to Table 1 for a list of
graph/hypergraph connectivity augmentation problems using edges/hyperedges,
previously known results, and our results.

Problem | Complexity Status
---|---
DS-Graph-CA-using-E | Strong Poly [28]
DS-Hypergraph-CA-using-E | NP-comp [22, 47]
DS-Hypergraph-CA-using-H | Psuedo Poly [58]
$O(n^{7}(n+m)^{2})$ time (Thm 1.1)
DS-Hypergraph-CA-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Thm 1.2)
DS-Simul-Hypergraph-CA-using-H | Pseudo Poly [8]
Strong Poly (Thm 1.3)
DS-Simul-Hypergraph-CA-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Thm 1.3)
Table 1: Complexity of Graph and Hypergraph Connectivity Augmentation Problems
using Edges and Hyperedges. Problems having “Near-Uniform” in their title are
similar to the corresponding problems without “Near-Uniform” in their title
but have the additional requirement that the returned solution hypergraph be
_near-uniform_. Here, $n$ and $m$ denote the number of vertices and hyperedges
respectively in the input hypergraph.

###  1.1 Degree-specified skew-supermodular cover problems

We focus on more general function cover problems that encompass several
applications in connectivity augmentation (including all hypergraph
connectivity augmentation problems mentioned above). Our main contribution is
the first strongly polynomial time algorithm for the more general function
cover problems. In Section 6, we will discuss several applications of our
results for the general function cover problems and in particular, will derive
Theorems 1.1, 1.2, and 1.3. We recall certain definitions needed to describe
the general problem.

######  Definition 1.1.

Let $V$ be a finite set, $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ be a hypergraph, and
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set function.

  1. 1.

The hypergraph $(H,w)$ _weakly covers_ the function $p$ if $b_{(H,w)}(X)\geq
p(X)$ for every $X\subseteq V$.

  2. 2.

The hypergraph $(H,w)$ _strongly covers_ the function $p$ if $d_{(H,w)}(X)\geq
p(X)$ for every $X\subseteq V$.

We will be interested in the problem of finding a degree-specified hypergraph
that strongly/weakly covers a given function $p$. In all our applications
(including DS-Hypergraph-CA-using-H), the function $p$ of interest will be
skew-supermodular and/or symmetric.

######  Definition 1.2.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow Z$ be a set
function. We will denote the maximum function value of $p$ by $K_{p}$, i.e.,
$K_{p}\coloneqq\max\\{p(X)\mathrel{\mathop{\mathchar 58\relax}}X\subseteq
V\\}$. The set function $p$

  1. 1.

is _symmetric_ if $p(X)=p(V-X)$ for every $X\subseteq V$, and

  2. 2.

is _skew-supermodular_ if for every $X,Y\subseteq V$, at least one of the
following inequalities hold:

    1. (a)

$p(X)+p(Y)\leq p(X\cap Y)+p(X\cup Y)$. If this inequality holds, then we say
that $p$ is _locally supermodular_ at $X,Y$.

    2. (b)

$p(X)+p(Y)\leq p(X-Y)+p(Y-X)$. If this inequality holds, then we say that $p$
is _locally negamodular_ at $X,Y$.

As mentioned above, we will be interested in the problem of finding a degree-
specified hypergraph that strongly/weakly covers a given skew-supermodular
function $p$. We will assume access to the skew-supermodular function $p$ via
the following oracle.

######  Definition 1.3.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set
function.
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}\left(\left(G_{0},c_{0}\right),S_{0},T_{0},y_{0}\right)$
takes as input a hypergraph $(G_{0}=(V,E_{0}),c_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\mathbb{Z}_{+})$, disjoint sets
$S_{0},T_{0}\subseteq V$, and a vector $y_{0}\in\R^{V}$; the oracle returns a
tuple $(Z,p(Z))$, where $Z$ is an optimum solution to the following problem:

$\displaystyle\max$
$\displaystyle\left\\{p(Z)-d_{(G_{0},c_{0})}(Z)+y_{0}(Z)\mathrel{\mathop{\mathchar
58\relax}}S_{0}\subseteq Z\subseteq V-T_{0}\right\\}.$
(${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$)

We note that
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is
strictly stronger than the function evaluation oracle111For a function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, the function
evaluation oracle takes a subset $X\subseteq V$ as input and returns $p(X)$. –
in particular, it is impossible to maximize a skew-supermodular function using
polynomial number of function evaluation queries [37]. However, we will see
later that ${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$
can indeed be implemented in strongly polynomial time for the functions $p$ of
interest to our applications. In our algorithmic results, we will ensure that
the size of hypergraphs $(G_{0},c_{0})$ used as inputs to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ are
polynomial in the input size (in particular, the number of hyperedges in these
hypergraphs will be polynomial in the size of the ground set $V$). We now
describe the general function cover problems that will be of interest to this
work.

##### Strong Cover Problems.

In all our applications, we will be interested in obtaining a degree-specified
strong cover of a function.

Degree-specified symmetric skew-supermodular strong cover using hyperedges
problem
(DS-Sym-Skew-SupMod-StrongCover-using-H). Given: A degree requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ and a symmeric
skew-supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Goal:
Verify if there exists a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ such that $b_{(H,w)}(u)=m(u)$ for every $u\in
V$, $(H,w)$ strongly covers the function $p$, and if so, then find such a
hypergraph.

DS-Sym-Skew-SupMod-StrongCover-using-H was introduced by Bernáth and Király
[8] as a generalization of DS-Hypergraph-CA-using-H (and various other
applications that we will discuss in Section 6). They showed that it is
impossible to solve DS-Sym-Skew-SupMod-StrongCover-using-H using polynomial
number of queries to the function evaluation oracle. They suggested access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and we
work in the same function access model as Bernáth and Király. We note that it
is not immediately clear if feasible instances of DS-Sym-Skew-SupMod-
StrongCover-using-H admit solution hypergraphs with polynomial number of
hyperedges (see Remark 1.1), so membership of DS-Sym-Skew-SupMod-StrongCover-
using-H in NP is not obvious.

Bernáth and Király [8] also introduced the following generalization of DS-
Simul-Hypergraph-CA-using-H.

Degree-specified simultaneous symmetric skew-supermodular strong cover using
hyperedges problem (DS-Simul-Sym-Skew-Skew-SupMod-StrongCover-using-H). Given:
A degree requirement function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ and symmetric skew-supermodular functions
$q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ via
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where
$K_{q}=K_{r}$. Goal: Verify if there exists a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ such that
$b_{(H,w)}(u)=m(u)$ for every $u\in V$ and $(H,w)$ strongly covers both
functions $q$ and $r$, and if so, then find such a hypergraph.

We note that DS-Simul-Sym-Skew-Skew-SupMod-StrongCover-using-H without the
assumption that $K_{q}=K_{r}$ is known to be NP-complete [8], so we include
this assumption in the problem definition.

##### Weak Cover Problems.

Although our applications will be concerned with degree-specified _strong_
cover, our techniques will be concerned with degree-specified _weak_ cover
problems. There is indeed a close relationship between strong cover and weak
cover of symmetric skew-supermodular functions that we elaborate now. If a
hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ strongly covers a function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, then it also
weakly covers the function $p$. However, the converse is false – i.e., a weak
cover is not necessarily a strong cover222For example, consider the function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ defined by
$p(X)\coloneqq 1$ for every non-empty proper subset $X\subsetneq V$ and
$p(\emptyset)\coloneqq p(V)\coloneqq 0$, and the hypergraph
$(H=(V,E\coloneqq\\{\\{u\\}\mathrel{\mathop{\mathchar 58\relax}}u\in
V\\}),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\\{1\\})$.. Bernáth
and Király [8] showed that if a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ with
$\sum_{e\in E}w(e)=K_{p}$ weakly covers a symmetric skew-supermodular function
$p$, then $(H,w)$ strongly covers $p$. Moreover, Szigeti [58] showed that if
DS-Sym-Skew-SupMod-StrongCover-using-H is feasible, then it admits a solution
hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ such that $\sum_{e\in E}w(e)=K_{p}$. These two
facts together imply that in order to solve DS-Sym-Skew-SupMod-StrongCover-
using-H, it suffices to solve a degree-specified skew-supermodular _weak_
cover using hyperedges problem for the same function $p$. We define the latter
problem now.

Degree-specified skew-supermodular weak cover using hyperedges problem (DS-
Skew-SupMod-WeakCover-using-H). Given: A degree requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ and a skew-
supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Goal:
Verify if there exists a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ such that $b_{(H,w)}(u)=m(u)$ for every $u\in
V$, $(H,w)$ weakly covers the function $p$, and $\sum_{e\in E}w(e)=K_{p}$, and
if so, then find such a hypergraph.

We clarify the significance of the requirement $\sum_{e\in E}w(e)=K_{p}$ in
the above problem (we note that this requirement is not present in DS-Sym-
Skew-SupMod-StrongCover-using-H). In DS-Skew-SupMod-WeakCover-using-H, if we
drop the requirement that $\sum_{e\in E}w(e)=K_{p}$ from the problem
definition, then the resulting problem admits a feasible solution if and only
if a trivial hypergraph is feasible333Consider the hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$, where
$E\mathrel{\mathop{\mathchar 58\relax}}=\\{\\{u\\}\mathrel{\mathop{\mathchar
58\relax}}u\in V,\ m(u)\geq 1\\}$ with $w(\\{u\\})\mathrel{\mathop{\mathchar
58\relax}}=m(u)$ for every $\\{u\\}\in E$.. Imposing this requirement makes
the problem non-trivial. More importantly, imposing this requirement ensures
that we have a reduction from DS-Sym-Skew-SupMod-StrongCover-using-H to DS-
Skew-SupMod-WeakCover-using-H.

Next, in order to address DS-Simul-Sym-Skew-Skew-SupMod-StrongCover-using-H,
Bernáth and Király [8] showed the following two results: (1) If a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ is a weak
cover of two symmetric skew-supermodular functions $q,r$ with $\sum_{e\in
E}w(e)=K_{p}$, then $(H,w)$ is also a strong cover of $p$. (2) If DS-Simul-
Sym-Skew-Skew-SupMod-StrongCover-using-H is feasible, then it admits a
solution hypergraph $(H,w)$ such that $\sum_{e\in E}w(e)=K_{p}$. These two
facts together imply that in order to solve DS-Simul-Sym-Skew-Skew-SupMod-
StrongCover-using-H, it suffices to solve a degree-specified skew-supermodular
_weak_ cover using hyperedges problem for the same functions $q$ and $r$. We
define the latter problem now.

Degree-specified simultaneous skew-supermodular weak cover using hyperedges
problem (DS-Simul-Skew-SupMod-WeakCover-using-H). Given: A degree requirement
function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ and
skew-supermodular functions $q,r\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ via
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Goal:
Verify if there exists a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ such that $b_{(H,w)}(u)=m(u)$ for every $u\in
V$, $(H,w)$ weakly covers both functions $q$ and $r$, and $\sum_{e\in
E}w(e)=\max\\{K_{q},K_{r}\\}$, and if so, then find such a hypergraph.

###  1.2 Results

As mentioned in the previous section, reductions from DS-Sym-Skew-SupMod-
StrongCover-using-H to DS-Skew-SupMod-WeakCover-using-H and also from DS-
Simul-Sym-Skew-Skew-SupMod-StrongCover-using-H to DS-Simul-Skew-SupMod-
WeakCover-using-H were already known. Hence, from a technical perspective, the
central problems of interest to this work will be the weak cover problems,
namely DS-Skew-SupMod-WeakCover-using-H and DS-Simul-Skew-SupMod-WeakCover-
using-H.

######  Remark 1.3.

It is not immediately clear if feasible instances of these two weak cover
problems admit solution hypergraphs in which the number of hyperedges is
polynomial in the number of vertices. We illustrate this issue for DS-Skew-
SupMod-WeakCover-using-H with an example (that is a modification of the
example in Remark 1.1): let $n\mathrel{\mathop{\mathchar 58\relax}}=|V|$ and
consider the degree requirement function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ given by $m(u)\mathrel{\mathop{\mathchar
58\relax}}=2^{n-1}-1$ for every $u\in V$ and the function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ given by
$p(X)\mathrel{\mathop{\mathchar 58\relax}}=2^{n-1}-1$ for every non-empty
proper subset $X\subsetneq V$, $p(V)\mathrel{\mathop{\mathchar
58\relax}}=2^{n}-n-1$, and $p(\emptyset)\mathrel{\mathop{\mathchar
58\relax}}=0$. We note that this function $p$ is skew-supermodular. Consider
the hypergraph $(H=(V,E_{H}),w_{H})$, where $E_{H}\mathrel{\mathop{\mathchar
58\relax}}=\\{e\subseteq V\mathrel{\mathop{\mathchar 58\relax}}|e|\geq 2\\}$
and all hyperedge weights are one. The hypergraph $(H,w_{H})$ is a feasible
solution to the input instance but the number of hyperedges in this hypergraph
is $2^{n}-n-1$ which is exponential in the number of vertices. Thus, a
necessary step in designing a polynomial-time algorithm for DS-Skew-SupMod-
WeakCover-using-H is to show that feasible instances admit a solution
hypergraph in which the number of hyperedges is polynomial in the input size.
For the instance $(m,p)$ mentioned above, the following hypergraph is feasible
and has only $3$ hyperedges: pick an arbitrary vertex $u\in V$ and consider
the hypergraph
$(H^{\prime}=(V,E^{\prime}),w^{\prime}\mathrel{\mathop{\mathchar
58\relax}}E^{\prime}\rightarrow\Z_{+})$, where the set of hyperedges is
$E^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=\\{\\{u\\},V-\\{u\\},V\\}$
and their weights are given by
$w^{\prime}(\\{u\\})=2^{n-1}-n=w^{\prime}(V-\\{u\\})$ and $w^{\prime}(V)=n-1$.

Szigeti [58] gave a complete characterization for the existence of a feasible
solution to DS-Skew-SupMod-WeakCover-using-H. His proof implies that if a
given instance is feasible, then it admits a solution hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ in which
the number of hyperedges is $K_{p}$; we note that $K_{p}$ need not be
polynomial in $|V|$. His proof also leads to a pseudo-polynomial time
algorithm to solve DS-Skew-SupMod-WeakCover-using-H (the algorithm is only
pseudo-polynomial time and not polynomial time since the number of hyperedges
in the returned hypergraph could be $K_{p}$ and hence, the run-time depends on
$K_{p}$). In this work, we show that feasible instances admit a solution with
$O(|V|)$ hyperedges and give a strongly polynomial-time algorithm to solve DS-
Skew-SupMod-WeakCover-using-H.

######  Theorem 1.4.

There exists an algorithm to solve DS-Skew-SupMod-WeakCover-using-H that runs
in time $O(|V|^{5})$ using $O(|V|^{4})$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where $V$
is the ground set of the input instance. Moreover, if the instance is
feasible, then the algorithm returns a solution hypergraph that contains
$O(|V|)$ hyperedges. For each query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ made by
the algorithm, the hypergraph $(G_{0},c_{0})$ used as input to the query has
$O(|V|)$ vertices and $O(|V|)$ hyperedges.

Bernáth and Király [8] strengthened Szigeti’s result via an LP-based approach.
They showed that if an instance of DS-Skew-SupMod-WeakCover-using-H is
feasible, then it admits a solution hypergraph that is near-uniform. Their
approach is also algorithmic, but the run-time of their algorithm is only
pseudo-polynomial (again, owing to the dependence on $K_{p}$ which may not be
polynomial in $|V|$). In this work, we give a strongly polynomial-time
algorithm to solve DS-Skew-SupMod-WeakCover-using-H and return a near-uniform
solution hypergraph for feasible instances.

######  Theorem 1.5.

There exists an algorithm to solve DS-Skew-SupMod-WeakCover-using-H that runs
in $\poly(|V|)$ time using $\poly(|V|)$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where $V$
is the ground set of the input instance. Moreover, if the instance is
feasible, then the algorithm returns a solution hypergraph that is near-
uniform and contains $O(|V|)$ hyperedges. For each query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ made by
the algorithm, the hypergraph $(G_{0},c_{0})$ used as input to the query has
$O(|V|)$ vertices and $O(|V|)$ hyperedges.

Bernáth and Király’s [8] LP-based approach also helped in addressing DS-Simul-
Skew-SupMod-WeakCover-using-H. They gave a complete characterization for the
existence of a feasible solution to DS-Simul-Skew-SupMod-WeakCover-using-H.
Moreover, they showed that if an instance of DS-Simul-Skew-SupMod-WeakCover-
using-H is feasible, then it admits a solution hypergraph that is near-
uniform. Their proof is algorithmic, but the run-time of their algorithm is
only pseudo-polynomial (again, owing to the dependence on $K_{p}$ which may
not be polynomial in $|V|$). In this work, we give a strongly polynomial-time
algorithm to solve DS-Simul-Skew-SupMod-WeakCover-using-H and return a near-
uniform solution hypergraph for feasible instances.

######  Theorem 1.6.

There exists an algorithm to solve DS-Simul-Skew-SupMod-WeakCover-using-H that
runs in $\poly(|V|)$ time using $\poly(|V|)$ queries to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where $V$
is the ground set of the input instance. Moreover, if the instance is
feasible, then the algorithm returns a solution hypergraph that is near-
uniform and contains $O(|V|^{2})$ hyperedges. 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}$ made by
the algorithm, the hypergraph $(G_{0},c_{0})$ used as input to the query has
$O(|V|)$ vertices and $O(|V|^{2})$ hyperedges.

Our algorithm for Theorem 1.4 is combinatorial and hence, we are able to
provide an explicit bound on the run-time. In contrast, our algorithms for
Theorems 1.5 and 1.6 are LP-based. These LPs are solvable in strongly
polynomial time, but their run-time is large, so we refrain from stating the
run-times explicitly. We refer to Table 2 for a list of degree-specified skew-
supermodular cover using hyperedges problems, previously known results, and
our results. The results for strong cover problems follow from our results for
weak cover problems. We will later see that our results for strong cover
problems imply Theorems 1.1, 1.2, and 1.3 respectively (in Section 6).

Problem | Complexity Status
---|---
DS-Skew-SupMod-WeakCover-using-H | Pseudo Poly [58]
Strong Poly (Thm 1.4)
DS-Skew-SupMod-WeakCover-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Thm 1.5)
DS-Simul-Skew-SupMod-WeakCover-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Thm 1.6)
DS-Sym-Skew-SupMod-StrongCover-using-H | Pseudo Poly [58]
Strong Poly (Coro 6.4)
DS-Sym-Skew-SupMod-StrongCover-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Coro 6.5)
DS-Simul-Sym-Skew-SupMod-StrongCover-using-near-uniform-H | Pseudo Poly [8]
Strong Poly (Coro 6.6)
Table 2: Complexity of degree-specified skew-supermodular cover using
hyperedges problems. Problems having “Near-Uniform” in their title are similar
to the corresponding problems without “Near-Uniform” in their title but have
the additional requirement that the returned solution hypergraph be _near-
uniform_.

###  1.3 Techniques: Structural and Algorithmic Results

In this section, we discuss our techniques underlying the proof of Theorems
1.4, 1.5, and 1.6. For a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\R$, we denote $m(X)\coloneqq\sum_{u\in X}m(u)$.

#####  DS-Skew-SupMod-WeakCover-using-H.

Szigeti [58] showed that an instance $(m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0},p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z)$ of DS-Skew-SupMod-WeakCover-using-H is feasible
if and only if $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$
for every $u\in V$. We note that this characterization immediately implies
that feasibility of a given instance of DS-Skew-SupMod-WeakCover-using-H can
be verified using two calls to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. In the
algorithmic problem, we are interested in finding a feasible solution (i.e., a
hypergraph $(H,w)$) under the hypothesis that $m(X)\geq p(X)$ for every
$X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$. We show that every
feasible instance admits a feasible solution $(H,w)$ such that the number of
hyperedges in $H$ is linear in the number of vertices and moreover, such a
solution can be found in strongly polynomial time.

######  Theorem 1.7.

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 such that:

  1. $(a)$

$m(X)\geq p(X)$ for every $X\subseteq V$ and

  2. $(b)$

$m(u)\leq K_{p}$ for every $u\in V$.

Then, there exists a hypergraph
$\left(H=\left(V,E\right),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ satisfying the following four properties:

  1. $(1)$

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

  2. $(2)$

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

  3. $(3)$

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

  4. $(4)$

$|E|=O(|V|)$.

Furthermore, given a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ and access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ of a skew-
supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ where $m$ and $p$ satisfy conditions (a) and (b)
above, there exists an algorithm that runs in time $O(|V|^{5})$ using
$O(|V|^{4})$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
returns a hypergraph satisfying properties (1)-(4) above. The run-time
includes the time to construct the hypergraphs that are used as inputs 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 $O(|V|)$ vertices
and $O(|V|)$ hyperedges.

#####  DS-Skew-SupMod-WeakCover-using-H with near-uniform hyperedges.

Bernáth and Király [8] generalized Szigeti’s result with an LP-based approach.
They showed that every feasible instance of DS-Skew-SupMod-WeakCover-using-H
admits a near-uniform hypergraph as a feasible solution. In the algorithmic
problem, we are interested in finding a feasible solution under the hypothesis
that $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every
$u\in V$. We show that every feasible instance admits a feasible near-uniform
hypergraph $(H,w)$ as a solution such that the number of hyperedges in $H$ is
linear in the number of vertices and moreover, such a solution can be found in
strongly polynomial time.

######  Theorem 1.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 the
following two conditions:

  1. $(a)$

$m(X)\geq p(X)$ for every $X\subseteq V$ and

  2. $(b)$

$m(u)\leq K_{p}$ for every $u\in V$.

Then, there exists a hypergraph
$\left(H=\left(V,E\right),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ satisfying the following five properties:

  1. $(1)$

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

  2. $(2)$

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

  3. $(3)$

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

  4. $(4)$

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

  5. $(5)$

$|E|=O(|V|)$.

Furthermore, given a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ and access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ of a skew-
supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ where $m$ and $p$ satisfy conditions (a) and
(b), there exists an algorithm that runs in time $\poly(|V|)$ using
$\poly(|V|)$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ to return
a hypergraph satisfying the above five properties. The run-time includes the
time to construct the hypergraphs that are used as inputs 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 $O(|V|)$ vertices
and $O(|V|)$ hyperedges.

#####  DS-Simul-Skew-SupMod-WeakCover-using-H.

Bernáth and Király [8] showed that an instance $(m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0},q\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z,r\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z)$ of DS-Simul-Skew-SupMod-WeakCover-using-H is
feasible if and only if $m(Z)\geq p(Z)$ for all $Z\subseteq V$ and $m(u)\leq
K_{p}$ for all $u\in V$, where $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is the function defined by
$p(Z)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{q(Z),r(Z)\\}$ for all
$Z\subseteq V$. Moreover, they also showed that every feasible instance admits
a near-uniform hypergraph as a feasible solution. We show that every feasible
instance $(m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq
0},q\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z,r\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z)$ admits a near-uniform hypergraph $(H,w)$ as a
feasible solution such that the number of hyperedges in $H$ is quadratic in
the number of vertices and moreover, such a solution can be found in strongly
polynomial time.

######  Theorem 1.9.

Let $q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be two skew-
supermodular functions and $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ be the function defined as
$p(X)\coloneqq\max\left\\{q(X),r(X)\right\\}$ for every $X\subseteq V$.
Furthermore, let $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq
0}$ be a non-negative function satisfying the following two conditions:

  1. $(a)$

$m(X)\geq p(X)$ for every $X\subseteq V$ and

  2. $(b)$

$m(u)\leq K_{p}$ for every $u\in V$.

Then, there exists a hypergraph
$\left(H=\left(V,E\right),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ satisfying the following five properties:

  1. $(1)$

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

  2. $(2)$

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

  3. $(3)$

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

  4. $(4)$

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

  5. $(5)$

$|E|=O(|V|^{2})$.

Furthermore, given a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ and access to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ of skew-
supermodular functions $q,r\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ where $m$, $q$, and $r$ satisfy conditions (a)
and (b), there exists an algorithm that runs in time $\poly(|V|)$ using
$\poly(|V|)$ queries to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ to return
a hypergraph satisfying the above five properties. The run-time includes the
time to construct the hypergraphs that are used as inputs to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$
${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 $O(|V|)$ vertices
and $O(|V|^{2})$ hyperedges.

We note that conditions (a) and (b) and properties (1)-(4) in Theorems 1.8 and
1.9 are identical, but the hypothesis about the function $p$ is different
between the two theorems. Moreover, property (5) also differs between the two
theorems.

Theorem 1.7 is a strengthening of Szigeti’s result [58] in two ways. Szigeti
showed that if $m$ and $p$ are two functions satisfying conditions (a) and (b)
of the theorem, then there exists a hypergraph satisfying properties (1)-(3).
Our Theorem 1.7 strengthens his result by additionally showing property (4)
(i.e., the number of hyperedges is polynomial in the number of vertices) and
designing a strongly polynomial time algorithm that returns a hypergraph
satisfying the four properties. Theorems 1.8 and 1.9 are strengthenings of
Bernáth and Király’s results [8] in two ways. Bernáth and Király showed that
if conditions (a) and (b) of the theorem hold, then there exists a hypergraph
satisfying properties (1)-(4). Our Theorems 1.8 and 1.9 strengthen their
result by additionally showing property (5) (i.e., the number of hyperedges is
polynomial in the number of vertices) and designing a strongly polynomial time
algorithm that returns a hypergraph satisfying the five properties. Although
Szigeti’s result [58] and Bernáth and Király’s results [8] are existential,
their proof of their result is algorithmic. However, their proof is based on
induction on $K_{p}$ and consequently, the upper bound on the number of
hyperedges in the returned solution as well as their run-time is $O(K_{p})$.
Thus, the best run-time known for their algorithms is only pseudo-polynomial.
Our main contribution is analyzing an adaptation of their algorithm to bound
the number of hyperedges and the run-time.

Our algorithm for Theorem 1.7 is combinatorial while the algorithms for
Theorems 1.8 and 1.9 are LP-based. We show that the underlying LPs are
solvable in strongly polynomial-time in the technical sections. Theorems 1.7,
1.8, and 1.9 imply Theorems 1.4, 1.5, and 1.6 respectively.

####  1.3.1 Proof Technique for Theorem 1.7

In this section, we describe our proof technique for Theorem 1.7. The
algorithmic result in Theorem 1.7 follows from our techniques for the
existential result using known tools for submodular functions. So, we focus on
describing our proof technique for the existial result here. 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 such that
$m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in
V$. Our goal is to show that there exists a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ such that
(1) $(H,w)$ weakly covers the function $p$, (2) $b_{(H,w)}=m(u)$ for every
$u\in V$, (3) $\sum_{e\in E}w(e)=K_{p}$, and (4) $|E|=O(|V|)$. Our proof of
the existential result builds on the techniques of Szigeti [58] who proved the
existence of a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ satisfying properties (1)-(3), so we briefly
recall his techniques. His proof proceeds by picking a minimal counterexample
and arriving at a contradiction. Consequently, the algorithm implicit in the
proof is naturally recursive. We present the algorithmic version of the proof
since it will be useful for our purposes.

For the purposes of the algorithmic proof, we assume that $m$ is a positive-
valued function. We show that this assumption is without loss of generality
since an arbitrary instance can be reduced to such an instance (for details,
see the proof overview paragraph immediately following the restatement of
Theorem 1.7 in Section 4). The main insight underlying the proof is the
following characterization of hyperedges in a feasible hypergraph.

######  Proposition 1.1.

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(X)\geq p(X)$
for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$. Let
$A\subseteq V$. Then, there exists a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$
satisfying properties (1)-(3) such that $A\in E$ if and only if $A$ satisfies
the following:

  1. (i)

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

  2. (ii)

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

  3. (iii)

$m(v)\geq 1$ for each $v\in A$, and

  4. (iv)

$m(X)-|A\cap X|\geq p(X)-1$ for every $X\subseteq V$.

##### Algorithm of [58].

Proposition 1.1 leads to the following natural recursive strategy to compute a
feasible hypergraph. If $K_{p}=0$, then the algorithm is in its base case and
returns the empty hypergraph (with no vertices) – here, we note that
$0<m(u)\leq K_{p}=0$ for every $u\in V$, and consequently, $V=\emptyset$ and
thus, the empty hypergraph satisfies properties (1)-(3) as desired.
Alternatively, if $K_{p}>0$, then the algorithm recurses on appropriately
revised versions of the input functions $p$ and $m$. In particular, the
algorithm picks an arbitrary minimal transversal $T$ for the family of
$p$-maximizers and computes the set $A\mathrel{\mathop{\mathchar
58\relax}}=T\cup\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}m(u)=K_{p}\\}$.
It can be shown that this set $A$ satisfies properties (i)-(iv) of Proposition
1.1; consequently, there exists a feasible hypergraph containing the hyperedge
$A$. In order to revise the input functions, the algorithm defines
$(H_{0},w_{0})$ to be the hypergraph on vertex set $V$ consisting of the
single hyperedge $A$ with weight $w_{0}(A)=1$ and constructs the set
$\mathcal{Z}\mathrel{\mathop{\mathchar 58\relax}}=\\{u\in
A\mathrel{\mathop{\mathchar 58\relax}}m(u)=1\\}$. Next, the algorithm defines
revised functions $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z$ and
$p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V-\mathcal{Z}}\rightarrow\Z$ as
$m^{\prime\prime}(u)\mathrel{\mathop{\mathchar 58\relax}}=m(u)-1$ if $u\in
A-\mathcal{Z}$ and $m^{\prime\prime}(u)\mathrel{\mathop{\mathchar
58\relax}}=m(u)$ if $u\in V-A-\mathcal{Z}$ and
$p^{\prime\prime}(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{p(X\cup
R)-b_{(H_{0},w_{0})}(X\cup R)\mathrel{\mathop{\mathchar
58\relax}}R\subseteq\mathcal{Z}\\}$ for every $X\subseteq V-\mathcal{Z}$. The
algorithm recurses on the revised input functions $m^{\prime\prime}$ and
$p^{\prime\prime}$ to obtain a hypergraph
$(H^{\prime\prime},w^{\prime\prime})$. Finally, the algorithm obtains the
hypergraph $(G,c)$ by adding vertices $\mathcal{Z}$ to
$(H^{\prime\prime},w^{\prime\prime})$, and returns the hypergraph
$(G+H_{0},c+w_{0})$. It can be shown that $p^{\prime\prime}$ is a skew-
supermodular function and $m^{\prime\prime}$ is a positive function such that
$m^{\prime\prime}(X)\geq p^{\prime\prime}(X)$ for all $X\subseteq
V-\mathcal{Z}$ and $m^{\prime\prime}(u)\leq K_{p^{\prime\prime}}$ for every
$u\in V-\mathcal{Z}$. We note that $K_{p^{\prime\prime}}=K_{p}-1$ by the
definition of the function $p^{\prime\prime}$ and the choice of set $A$ being
a transversal for the family of $p$-maximizers. Consequently, by induction on
$K_{p}$ and Proposition 1, the algorithm can be shown to terminate in $K_{p}$
recursive calls and return a hypergraph $(H,w)$ satisfying properties (1)-(3).
Furthermore, we observe that the number of distinct hyperedges added by the
algorithm is at most the number of recursive calls since each recursive call
adds at most one new hyperedge to $(H,w)$. Thus, the number of distinct
hyperedges in $(H,w)$ is also at most $K_{p}$. Consequently, in order to
reduce the number of distinct hyperedges, it suffices to reduce the recursion
depth of Szigeti’s algorithm. We note that there exist inputs for which
Szigeti’s algorithm can indeed witness an execution with exponential recursion
depth, and consequently may construct only exponential sized hypergraphs on
those inputs (see example in Remark 1.3). So, we necessarily have to modify
his algorithm to reduce the recursion depth.

##### Our Algorithm.

We now describe our modification of Szigeti’s algorithm to reduce the
recursion depth. We observe that the hyperedge $A$ chosen during a recursive
call of Szigeti’s algorithm could also be the hyperedge chosen during a
subsequent recursive call. In fact, this could repeat for several consecutive
recursive calls before the algorithm cannot pick the hyperedge $A$ anymore. We
avoid such a sequence of consecutive recursive calls by picking as many copies
of the hyperedge $A$ as possible into the hypergraph $(H_{0},w_{0})$ (i.e.,
set the weight to be the number of copies picked) and revising the input
functions $m$ and $p$ accordingly for recursion. We describe this formally
now. Let $(p,m)$ be the input tuple and $A\subseteq V$ be as defined by
Szigeti’s algorithm. Let

$\alpha=\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\\}\end{cases}$

We construct the hypergraph $(H_{0},w_{0})$ on vertex set $V$ consisting of a
single hyperedge $A$ with weight $w_{0}(A)=\alpha$. Next, we proceed similarly
to Szigeti’s algorithm as follows: We construct the sets
$\mathcal{Z}\mathrel{\mathop{\mathchar 58\relax}}=\\{u\in
A\mathrel{\mathop{\mathchar 58\relax}}m(u)=\alpha\\}$ and
$V^{\prime\prime}\mathrel{\mathop{\mathchar 58\relax}}=V-\mathcal{Z}$. Next,
we define the set function $p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V^{\prime\prime}}\rightarrow\Z$ as
$p^{\prime\prime}(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{p(X\cup
R)-b_{(H_{0},w_{0})}(X\cup R)\mathrel{\mathop{\mathchar
58\relax}}R\subseteq\mathcal{Z}\\}$ for every $X\subseteq V^{\prime\prime}$,
and the function $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V^{\prime\prime}\rightarrow\Z$ as
$m^{\prime\prime}(u)\mathrel{\mathop{\mathchar
58\relax}}=m(u)-\alpha\mathbbm{1}_{u\in A}$ for every $u\in V^{\prime\prime}$,
where $\mathbbm{1}_{u\in A}$ evaluates to one if $u\in A$ and evaluates to
zero otherwise. Next, we recurse on the input tuple
$(p^{\prime\prime},m^{\prime\prime})$ to obtain a hypergraph
$(H^{\prime\prime},w^{\prime\prime})$; obtain the hypergraph $(G,c)$ by adding
vertices $\mathcal{Z}$ to $(H^{\prime\prime},w^{\prime\prime})$, and return
$(G+H_{0},c+w_{0})$.

##### Recursion Depth Analysis.

By induction on $K_{p}$ (generalizing Szigeti’s proof), it can be shown that
our algorithm returns a hypergraph satisfying properties (1)-(3) of Theorem
1.7 and also terminates within finite number of recursive calls. We now sketch
our proof to show a strongly polynomial bound on the recursion depth of our
modified algorithm. For this, we consider how the value $\alpha$ is computed.
We recall that by our min-max relation, $\alpha$ is the minimum of the three
values $\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)}\\}$. Using this, we identify
a potential function which strictly increases with the recursion depth. For
this, we consider three set families that we define now. Let $\ell$ be the
recursion depth of the algorithm on an input instance and let $i\in[\ell]$.
Let $\mathcal{Z}_{i}$ be the set $\mathcal{Z}$ and $\calD_{i}$ be the set
$\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}m(u)=K_{p}\\}$ in the $i^{th}$
recursive call. Let $\mathcal{F}_{i}$ be the family of inclusionwise minimal
$p$-maximizers where $p$ is the set function input to the $i^{th}$ recursive
call (a set $X$ is a $p$-maximizer if $p(X)=K_{p}$). Let $\mathcal{Z}_{\leq
i}\mathrel{\mathop{\mathchar 58\relax}}=\cup_{j=1}^{i}\mathcal{Z}_{j}$ and
$\mathcal{F}_{\leq i}\mathrel{\mathop{\mathchar
58\relax}}=\cup_{j=1}^{i}\mathcal{F}_{j}$. We consider the potential function
$\phi(i)\mathrel{\mathop{\mathchar 58\relax}}=|\mathcal{Z}_{\leq
i}|+|\mathcal{F}_{\leq i}|+|\calD_{i}|$ and show that each of the three terms
in the function is non-decreasing with $i$. Furthermore, if $\alpha$ is
determined by $\alpha^{(1)}$, then $|\mathcal{Z}_{\leq i}|$ strictly
increases; if $\alpha$ is determined by $\alpha^{(2)}$, then
$|\mathcal{F}_{\leq i}|$ strictly increases; and if $\alpha$ is determined by
$\alpha^{(3)}$, then $|\calD_{i}|$ strictly increases (see Lemma 4.7). We note
that $\mathcal{Z}_{\leq\ell}\subseteq V$ and $\calD_{\ell}\subseteq V$.
Moreover, we examine how the input functions $p$ across recursive calls relate
to each other (see Lemma 4.8) and exploit skew-supermodularity of $p$ to show
that the family $\mathcal{F}_{\leq\ell}$ is _laminar_ over the ground set $V$
(see Lemma 3.2). These facts together imply that the recursion depth is at
most $4|V|-1$.

######  Remark 1.4.

Our main algorithmic contribution is the modification to Szigeti’s algorithm
to pick as many copies of a chosen hyperedge as possible during a recursive
call, i.e., pick hyperedge $A$ with weight $\alpha$ as opposed to weight $1$.
Without our modification, there exist inputs for which Szigeti’s original
algorithm can indeed witness an execution with exponential recursion depth,
and consequently may construct only exponential sized hypergraphs on those
inputs (see example in Remark 1.3). Our main analysis contribution is
identifying an appropriate potential function to show that our modified
algorithm indeed has linear recursion depth.

####  1.3.2 Proof Technique for Theorems 1.8 and 1.9

In this section, we describe our proof technique for Theorems 1.8 and 1.9. The
algorithmic result in both these theorems follow from our techniques for the
existential result using known tools for submodular functions. So, we focus on
describing our proof technique for the existential results here. We will
consider the setting of Theorem 1.9 since it is more general than the setting
of Theorem 1.8. We will distinguish between the two settings later after we
set up the background.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a function
such that $p(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{q(X),r(X)\\}$ for
every $X\subseteq V$, where $q,r\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ are skew-supermodular functions (we note that if
$p$ itself is skew-supermodular, then it corresponds to the setting of Theorem
1.8). Let $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$ be a
non-negative function satisfying (a) $m(X)\geq p(X)$ for every $X\subseteq V$
and (b) $m(u)\leq K_{p}$ for every $u\in V$. Our goal is to show that there
exists a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ such that (1) $(H,w)$ weakly covers the
function $p$, (2) $b_{(H,w)}=m(u)$ for every $u\in V$, (3) $\sum_{e\in
E}w(e)=K_{p}$, (4) $|e|\in\\{\lfloor m(V)/K_{p}\rfloor,\lceil
m(V)/K_{p}\rceil\\}$ for every $e\in E$ if $K_{p}>0$, and (5) $|E|=O(|V|)$.
Our proof of the existential result builds on the techniques of Bernáth and
Király [8] who proved the existence of a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$
satisfying properties (1)–(4), so we briefly recall their techniques. We
present the algorithmic version of their proof since it will be useful for our
purposes.

For the purposes of the algorithmic proof, we assume that $m$ is a positive-
valued function. We show that this assumption is without loss of generality
since an arbitrary instance can be reduced to such an instance (for details,
see the proof overview paragraph immediately following the restatement of
Theorem 1.8 and Theorem 1.9 in Sections 5.6 and 5.7 respectively). The proof
in [8] is inductive, and consequently, the algorithm implicit in their proof
is recursive. Central to their proof is the following polyhedron:

$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\\}.$

Bernáth and Király showed the following three properties of the polyhedron
$Q(p,m)$:

  1. (I)

An integer vector $y$ is in $Q(p,m)$ if and only if it is the indicator vector
of a hyperedge444The indicator vector of a hyperedge $e$ of a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ is the
vector $\chi_{e}\in\\{0,1\\}^{V}$ such that $\chi_{e}(u)=1$ if and only if
$u\in e$. in a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ satisfying properties (1)–(4),

  2. (II)

the polyhedron $Q(p,m)$ is non-empty, and

  3. (III)

The polyhedron $Q(p,m)$ is the intersection of two generalized polymatroids
(see Section B.2 for the definition of generalized polymatroid) and
consequently, all its extreme points are integral.

##### Algorithm of [8].

With these three properties, Bernáth and Király’s algorithm proceeds as
follows. If $K_{p}=0$, then the algorithm is in its base case and it returns
the empty hypergraph (with no vertices). Otherwise, $K_{p}>0$; the algorithm
picks a set $A\subseteq V$ whose indicator vector $\chi_{A}$ is in $Q(p,m)$ –
we note that such a set $A$ exists owing to Properties (II) and (III); with
this choice of the set $A$, the algorithm defines $(H_{0},w_{0})$ to be the
hypergraph on vertex set $V$ consisting of the single hyperedge $A$ with
weight $w_{0}(A)=1$. The fact that we have one hyperedge of the needed
hypergraph allows us to revise the functions $m$ and $p$ and recursively solve
the problem by relying on Property (I). We elaborate on how to revise and
recursively solve it now. The algorithm constructs the set
$\mathcal{Z}\mathrel{\mathop{\mathchar 58\relax}}=\\{u\in
A\mathrel{\mathop{\mathchar 58\relax}}m(u)=1\\}$. Next, the algorithm defines
revised functions $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z$ and
$p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V-\mathcal{Z}}\rightarrow\Z$ as
$m^{\prime\prime}(u)\mathrel{\mathop{\mathchar
58\relax}}=m(u)-\mathbbm{1}_{u\in A}$ for every $u\in V-\mathcal{Z}$, where
$\mathbbm{1}_{u\in A}$ evaluates to one if $u\in A$ and evaluates to zero
otherwise, and $p^{\prime\prime}(X)\mathrel{\mathop{\mathchar
58\relax}}=\max\\{p(X\cup R)-b_{(H_{0},w_{0})}(X\cup
R)\mathrel{\mathop{\mathchar 58\relax}}R\subseteq\mathcal{Z}\\}$ for every
$X\subseteq V-\mathcal{Z}$. Next, the algorithm recurses on the inputs
$m^{\prime\prime}$ and $p^{\prime\prime}$ to obtain a hypergraph
$(H_{0}^{*},w_{0}^{*})$. Finally, the algorithm obtains the hypergraph $(G,c)$
by adding vertices $\mathcal{Z}$ to $(H_{0}^{*},w_{0}^{*})$, and returns the
hypergraph $(G+H_{0},c+w_{0})$. It can be shown that $m^{\prime\prime}$ is a
positive function and there exist skew-supermodular functions
$q^{\prime\prime},r^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ such that
$p^{\prime\prime}(X)=\max\\{q^{\prime\prime}(X),r^{\prime\prime}(X)\\}$ for
each $X\subseteq V$ (if $p$ is skew-supermodular, then $p^{\prime\prime}$ is
also skew-supermodular). Moreover, it can also be shown that the functions
$p^{\prime\prime},m^{\prime\prime}$ satisfy conditions (a) and (b), and
$K_{p^{\prime\prime}}=K_{p}-1$. Consequently, by induction on $K_{p}$ and
Property (I), the algorithm can be shown to terminate in $K_{p}$ recursive
calls and returns a hypergraph $(H,w)$ satisfying properties (1)-(4).
Furthermore, we observe that the number of new hyperedges added by the
algorithm is at most the number of recursive calls since each recursive call
adds at most one new hyperedge to $(H,w)$. Thus, the number of hyperedges in
$(H,w)$ is also at most $K_{p}$. Consequently, in order to reduce the number
of new hyperedges, it suffices to reduce the recursion depth of this
algorithm.

##### Our Algorithm.

We now describe our modification of the above-mentioned Bernáth and Király’s
algorithm to reduce the recursion depth. We make two major modifications to
their algorithm. First, we observe that the hyperedge $A$ chosen for the input
tuple $(p,m)$ could be such that $\chi_{A}\in
Q(p^{\prime\prime},m^{\prime\prime})$, where
$(p^{\prime\prime},m^{\prime\prime})$ is the input for the next recursive call
and consequently, could be chosen as the hyperedge for the next recursive
call. In fact, this could repeat for several consecutive recursive calls
before we cannot use the hyperedge $A$ anymore. We avoid such a sequence of
consecutive recursive calls by picking as many copies of the hyperedge $A$ as
possible into the hypergraph $(H_{0},w_{0})$ (i.e., set the weight to be the
number of copies picked) and revising $m$ and $p$ accordingly. We describe
this formally now: Let $(p,m)$ be the input tuple and $A\subseteq V$ be as
defined by Szigeti’s algorithm. For $\beta\in\Z_{+}$, let
$(H_{0}^{\beta},w_{0}^{\beta})$ denote the hypergraph on vertex set $V$
consisting of a single hyperedge $A$ with weight $w_{0}^{\beta}(A)=\beta$. Let

$\alpha\mathrel{\mathop{\mathchar
58\relax}}=\max\left\\{\beta\in\Z_{+}\mathrel{\mathop{\mathchar
58\relax}}\chi_{A}\in
Q\left(p-b_{(H_{0}^{\beta},w_{0}^{\beta})},m-\beta\chi_{A}\right)\right\\}.$

We construct the hypergraph $(H_{0},w_{0})\mathrel{\mathop{\mathchar
58\relax}}=(H_{0}^{\alpha},w_{0}^{\alpha})$, sets
$\mathcal{Z}\mathrel{\mathop{\mathchar 58\relax}}=\\{u\in
A\mathrel{\mathop{\mathchar 58\relax}}m(u)=\alpha\\}$,
$V^{\prime\prime}\mathrel{\mathop{\mathchar 58\relax}}=V-\mathcal{Z}$, and
proceed similar to Bernáth and Király’s algorithm. In particular, we define
the revised inputs $p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V^{\prime\prime}}\rightarrow\Z$ as
$p^{\prime\prime}(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{p(X\cup
R)-b_{(H_{0},w_{0})}(X\cup R)\mathrel{\mathop{\mathchar
58\relax}}R\subseteq\mathcal{Z}\\}$ and
$m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V^{\prime\prime}\rightarrow\Z$ as
$m^{\prime\prime}(u)\mathrel{\mathop{\mathchar
58\relax}}=m(u)-\alpha\mathbbm{1}_{u\in A}$ for every $u\in V^{\prime\prime}$,
where $\mathbbm{1}_{u\in A}$ evaluates to one if $u\in A$ and evaluates to
zero otherwise. Our algorithm then recurses on the revised input tuple
$(p^{\prime\prime},m^{\prime\prime})$ to obtain a hypergraph
$(H_{0}^{*},w_{0}^{*})$, obtains the hypergraph $(G,c)$ by adding vertices
$\mathcal{Z}$ to $(H_{0}^{*},w_{0}^{*})$, and returns $(G+H_{0},c+w_{0})$.

Our second modification to Bernáth and Király’s algorithm is regarding the
hyperedge $A^{\prime\prime}$ chosen in the subsequent recursive call. To
initialize for an arbitrary input $(p,m)$, we pick an arbitrary hyperedge $A$
such that $\chi_{A}\in Q(p,m)$. However, in the subsequent recursive call, we
force the chosen hyperedge to be correlated with the hyperedge chosen in the
current call. Their algorithm would have picked an arbitrary set
$A^{\prime\prime}\subseteq V^{\prime\prime}$ whose indicator vector
$\chi_{A^{\prime\prime}}$ is in $Q(p^{\prime\prime},m^{\prime\prime})$.
Instead, we pick a set $A^{\prime\prime}$ that has the _largest overlap_ with
the set $A$ chosen in the immediate previous recursive call subject to
$\chi_{A^{\prime\prime}}\in Q(p^{\prime\prime},m^{\prime\prime})$.

##### Recursion Depth Analysis.

By induction on $K_{p}$ (generalizing Bernáth and Király’s proof), it can be
shown that our algorithm returns a hypergraph satisfying (1)–(4) and also
terminates within finite number of recursive calls. Here, we sketch our proof
to show that the recursion depth of our modified algorithm is polynomial in
the number of vertices. For this, we consider how the value $\alpha$ is
computed: We have five constraints describing the polyhedron $Q(p,m)$.
Consequently, the largest positive integer $\alpha$ such that $\chi_{A}\in
Q(p-b_{(H_{0}^{\alpha},w_{0}^{\alpha})},m-\alpha\chi_{A})$ is determined
(i.e., constrained tightly) by one of the five constraints. We show that
$\alpha$ can be determined by constraint (v) in at most one recursive call
(Lemma 5.6). Hence, it suffices to bound the number of recursive calls where
$\alpha$ is determined by one of the constraints (i)–(iv). Next, we bound the
number of recursive calls where $\alpha$ is determined by one of the
constraints (i)–(iii). For this, we consider three set families that we define
now: Let $\ell$ be the recursion depth of the algorithm on an input instance
and let $i\in[\ell]$. Let $\mathcal{Z}_{i}$ be the set $\mathcal{Z}$ and
$\calD_{i}$ be the set $\\{u\in V\mathrel{\mathop{\mathchar
58\relax}}m(u)=K_{p}\\}$ in the $i^{th}$ recursive call. Let $\mathcal{F}_{i}$
be the family of inclusionwise minimal $p$-maximizers where $p$ is the set
function input to the $i^{th}$ recursive call. Let $\mathcal{Z}_{\leq
i}\mathrel{\mathop{\mathchar 58\relax}}=\cup_{j=1}^{i}\mathcal{Z}_{j}$ and
$\mathcal{F}_{\leq i}\mathrel{\mathop{\mathchar
58\relax}}=\cup_{j=1}^{i}\mathcal{F}_{j}$. We consider the potential function
$\phi(i)\mathrel{\mathop{\mathchar 58\relax}}=|\mathcal{Z}_{\leq
i}|+|\mathcal{F}_{\leq i}|+|\calD_{i}|$ and show that each of the three terms
in the function is non-decreasing with $i$. Furthermore, if $\alpha$ is
determined by constraint (i), then $|\mathcal{Z}_{\leq i}|$ strictly
increases; if $\alpha$ is determined by constraint (ii), then
$|\mathcal{F}_{\leq i}|$ strictly increases; if $\alpha$ is determined by
constraint (iii), then $|\calD_{i}|$ strictly increases (see Lemma 5.10). We
note that $\mathcal{Z}_{\leq\ell}\subseteq V$ and $\calD_{\ell}\subseteq V$.
We exploit skew-supermodularity to show that $\mathcal{F}_{\leq\ell}$ is the
union of two laminar families over the ground set $V$ (see Lemma 3.2 and 5.8
in Lemma 5.25). These facts together imply that the number of recursive calls
where $\alpha$ is determined by one of the constraints (i)–(iii) is at most
$6|V|$. It remains to bound the number of recursive calls where $\alpha$ is
determined by constraint (iv). This is the challenging part of the proof. Our
proof strategy for covering one function differs from that for covering two
functions and we will describe them next.

##### Covering one function.

Here, we consider the case where the input function $p$ is skew-supermodular.
As mentioned before, the algorithm’s input function in each recursive call is
also skew-supermodular. To bound the number of recursive calls where $\alpha$
is determined by constraint (iv), we consider another set family. For an input
tuple $(p,m)$, we say that a set $X$ is _$(p,m)$ -tight_ if $p(X)=m(X)$. Let
$i\in[\ell]$. We define $T_{i}$ to be the family of $(p,m)$-tight sets where
the tuple $(p,m)$ is the input to the $i^{th}$ recursive call and
$\mathcal{T}_{i}$ to be the family of inclusionwise maximal sets in $T_{i}$.
In contrast to $\mathcal{F}_{\leq i}=\cup_{j=1}^{i}\mathcal{F}_{j}$, it is
possible that $\cup_{j=1}^{i}\mathcal{T}_{j}$ is not laminar. To overcome this
challenge, we define $\mathcal{T}_{\leq i}$ differently by considering the
projection of all tight sets to the ground set $V_{i}$ of the $i^{th}$
recursive call: we define $\mathcal{T}_{\leq 1}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{T}_{1}$ and $\mathcal{T}_{\leq
i}\mathrel{\mathop{\mathchar 58\relax}}=\mathcal{T}_{i}\cup\\{X\cap
V_{i}\mathrel{\mathop{\mathchar 58\relax}}X\in\mathcal{T}_{\leq i-1}\\}$ for
integers $i$ where $2\leq i\leq\ell$. We show that $\mathcal{T}_{\leq i}$ is
laminar for every $i\in[\ell]$ (see Lemma 5.19). However, $|\mathcal{T}_{\leq
i}|$ is not necessarily non-decreasing with $i$ since projection of a set
family to a subset could result in the loss of sets from the family. To
circumvent this issue, we consider the potential function
$\Phi(i)\mathrel{\mathop{\mathchar 58\relax}}=|\mathcal{F}_{\leq
i}|+|\mathcal{T}_{\leq i}|+3|\mathcal{Z}_{\leq i-1}|$ and show that it is non-
decreasing with $i$ (see Lemma 5.22). Next, it is tempting to show that if
$\alpha$ is determined by constraint (iv), then $\Phi(i)$ strictly increases,
but this is not necessarily true. Instead, by exploiting the second
modification in our algorithm – i.e., by correlating the hyperedge chosen in
the current recursive call with the hyperedge chosen in the immediate previous
recursive call, we show that if $\Phi(i)=\Phi(i+1)$ and $\alpha$ is determined
by constraint (iv) (but none of the other constraints) in the $i^{th}$
recursive call, then $\Phi(i+2)>\Phi(i)$ (see Lemma 5.22 which in turn relies
on Lemmas 5.20 and 5.21). We emphasize that this is the most challenging part
of the proof – it involves showing that new tight sets are formed at the end
of the $(i+1)^{th}$ recursive call assuming no progress to the potential
function in the $i^{th}$ recursive call; we prove this by exploiting the
correlated choice of $A^{\prime\prime}$ with $A$. The above arguments together
imply that the number of recursive calls where $\alpha$ is determined by
constraint (iv) is $O(|V|)$.

##### Covering two functions.

Here, we consider the case where the input function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ is such that
$p(X)=\max\\{q(X),r(X)\\}$ for every $X\subseteq V$, where
$q,r\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ are skew-
supermodular functions. We recall that the goal is to bound the number of
recursive calls where $\alpha$ is determined by constraint (iv). In the
setting of covering two functions, we are unable to adapt the strategy
mentioned above for covering one function – we were unable to show that new
tight sets are formed at the end of the $(i+1)^{th}$ recursive call assuming
$\Phi(i)=\Phi(i+1)$ and $\alpha$ is determined by constraint (iv) in the
$i^{th}$ recursive call. So, our proof strategy here is different.

For an input tuple $(p,m)$, we define the pairwise $(p,m)$-slack function
$\gamma_{p,m}(\\{u,v\\})\mathrel{\mathop{\mathchar
58\relax}}=\min\\{m(X)-p(X)\mathrel{\mathop{\mathchar 58\relax}}u,v\in
X\subseteq V\\}$ for every pair $\\{u,v\\}\in\binom{V}{2}$. As mentioned
before, the algorithm’s input function $(p_{i}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{i}}\rightarrow\Z,m_{i}\mathrel{\mathop{\mathchar
58\relax}}V_{i}\rightarrow\Z_{\geq 0})$ in the $i^{th}$ recursive call
satisfies $m_{i}(X)\geq p_{i}(X)$ for every $X\subseteq V_{i}$. Consequently,
the pairwise slack function $\gamma_{p_{i},m_{i}}(\\{u,v\\})$ is non-negative
for every pair $u,v\in\binom{V_{i}}{2}$. We show that
$\gamma_{p_{i+1},m_{i+1}}(\\{u,v\\})\leq\gamma_{p_{i},m_{i}}(\\{u,v\\})$ for
every pair $\\{u,v\\}\in\binom{V_{i+1}}{2}$ – i.e., the pairwise slack
function is non-increasing (see Lemma 5.23). Moreover, if $\alpha$ is
determined by constraint (iv) in the $i^{th}$ recursive call, then there
exists a set $Z\subseteq V$ such that $|A\cap Z|\geq 2$ and
$\gamma_{p_{i+1},m_{i+1}}(\\{u,v\\})<\min\\{|A\cap
Z|-1,\gamma_{p_{i},m_{i}}(\\{u,v\\})\\}$ for every pair
$\\{u,v\\}\in\binom{A\cap Z}{2}$, where $A$ is the hyperedge chosen in the
$i^{th}$ recursive call (see Lemma 5.24). Now, we define the potential
function $\Phi(i)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{\\{u,v\\}\in\binom{V_{i}}{2}}\sum_{j=1}^{\gamma_{p_{i},m_{i}}(u,v)}(1/j^{2})$
and show that it is non-increasing. Moreover, if $\alpha$ is determined by
constraint (iv) in the $i^{th}$ recursive call, then
$\Phi(i+1)\leq\Phi(i)-1/4$ (5.7 in Lemma 5.25). Finally, we have that
$\Phi(1)=O(|V|^{2})$. Consequently, the number of recursive calls where
$\alpha$ is determined by constraint (iv) is $O(|V|^{2})$. We emphasize that
our proofs for covering two functions _do not_ exploit the third modification
that we made to Bernáth and Király’s algorithm.

######  Remark 1.5.

Our algorithmic contributions are the two modifications to Bernáth and
Király’s algorithm: (1) We allow picking as many copies of a chosen hyperedges
as possible during a recursive call (i.e., pick hyperedge $A$ with weight
$\alpha$ as opposed to weight $1$). (2) We correlate the choice of the
hyperedge $A$ in the current recursive call with the immediate previous
recursive call. The first modification is necessary to bound the recursion
depth to be polynomial in the size of the ground set $V$. The second
modification is not necessary to bound the recursion depth to be polynomial in
the size of the ground set $V$. The first modification already suffices for
this purpose. We exploit the second modification in the setting of covering
one function to improve the recursion depth from quadratic to linear in the
size of the ground set.

######  Remark 1.6.

Our main analysis contribution is identifying appropriate potential functions
to measure progress of our modified algorithm. For covering two functions, we
identified the notion of pairwise slack functions, showed progress for these
functions, and devised a potential function that combined pairwise slack
functions to show global progress. For the improved bound for covering one
function, we exploited the correlated choice of the hyperedges chosen in two
consecutive recursive calls to show quantifiable progress within two recursive
calls.

###  1.4 Related Work

In network design problems, the goal is to construct a graph that has certain
pre-specified properties. This is a broad family of problems encompassing
polynomial-time solvable problems like minimum cost spanning tree and shortest
$(s,t)$-path as well as NP-hard problems like Steiner Tree and Tree
Augmentation. The polynomial-time solvable network design problems have been
studied from the perspective of fast algorithms while the NP-hard network
design problems have been studied from the perspective of approximation
algorithms leading to a rich toolkit of techniques on both fronts (e.g., see
[30, 48, 54, 62, 55, 56]). In this section, we mention related works on
_hypergraph_ network design problems.

Hypergraph cut/coverage/spectral sparsifiers can be viewed as special cases of
hypergraph network design problems. Here, the input is a hypergraph and the
goal is to construct a sub-hypergraph (i.e., the hyperedges in the constructed
hypergraph form a subset of the hyperedges of the input hypergraph and their
weights are allowed to be different from the input hypergraph) with few
hyperedges in order to approximately preserve cut and/or coverage values of
all subsets of vertices and/or spectral values of all vectors on $V$
coordinates where $V$ is the vertex set of the input hypergraph. Recent works
have shown the existence of cut/coverage/spectral sparsifiers where the number
of hyperedges is near-linear in the number of vertices and that they can be
constructed in time that is near-linear in the size of the input hypergraph
[43, 19, 57, 2, 20, 41, 40, 45, 39, 52]. These results do not have direct
implications for the problems that we study in our work since we focus on
degree-specified network design problems. Even if we relax the degree-
specification requirement, these results only imply the _existence_ of
hypergraphs with near-linear number of hyperedges that satisfy certain kinds
of cut/coverage requirements _approximately_. In contrast, our work focuses on
efficient algorithmic construction of small-sized hypergraphs that satisfy
cut/coverage requirements exactly.

The rank of a hypergraph is the size of its largest hyperedge. Degree-
specified hypergraph local connectivity augmentation using _rank- $t$_
hyperedges of minimum total weight problem is a variant of DS-Hypergraph-CA-
using-H where the returned hypergraph is additionally required to have rank at
most $t$ (where $t$ is an input integer). Thus, DS-Hypergraph-CA-using-E is a
special case of degree-specified hypergraph local connectivity augmentation
using rank-$2$ hyperedges. Although DS-Graph-CA-using-E is polynomial-time
solvable [65, 12, 29, 28, 32, 10, 49, 5, 6, 44], DS-Hypergraph-CA-using-E is
NP-hard (i.e., hypergraph local connectivity augmentation using edges of
minimum total weight is NP-hard) [22]. In a surprising twist, independent
works by Cosh [21], Nutov [50], and Bernáth and Király [9] have shown that
feasible instances of DS-Hypergraph-CA-using-H admit a solution with at most
one hyperedge of size at least $3$ while all other hyperedges are in fact
size-$2$ edges. Their results are also applicable to DS-Sym-Skew-SupMod-
StrongCover-using-H. We note that their proof technique does not generalize to
obtain near-uniform hyperedges or to address simultaneous cover of two
functions.

##  2 Preliminaries

##### Projection of Laminar Families.

We recall that two sets $X,Y\subseteq V$ are said to cross if the sets
$X-Y,Y-X,X\cap Y$ are non-empty. A family $\calL\subseteq 2^{V}$ is _laminar_
if no two sets in $\calL$ cross. We will be interested in the _projection_ of
a laminar family, i.e., the restriction of a laminar family $\calL\subseteq
2^{V}$ to a ground set $V-\calZ$ for some $\calZ\subseteq V$. The next lemma
from [7] says that the size of the projection is comparable to that of the
original family $\calL$.

######  Lemma 2.1 (Lemma 2.1 of [7]).

Let $\calL\subseteq 2^{V}$ be a laminar family and $\calZ\subseteq V$ be a
subset of elements. Let
$\calL^{\prime}\coloneqq\\{X-\calZ\mathrel{\mathop{\mathchar
58\relax}}X\in\calL\\}-\\{\emptyset\\}$. Then, the family $\calL^{\prime}$ is
a laminar family and $|\calL|\leq|\calL^{\prime}|+3|\calZ|$.

##### Maximization Oracles.

We recall that in our algorithmic problems, we have access to the input set
function $p$ via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. We
describe two additional oracles that will simplify our proofs. We will show
that both oracles defined below can be implemented in strongly polynomial time
using ${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.

######  Definition 2.1 ($p$-maximization oracles).

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set
function. We define two oracles for the set function $p$. Both oracles take as
input disjoint sets $S_{0},T_{0}\subseteq V$, and a vector ${y_{0}}\in\R^{V}$.

  1. 1.

${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}\left(\left({G_{0}},{w_{0}}\right),S_{0},T_{0},{y_{0}}\right)$
additionally takes a hypergraph
$(G_{0}=(V,E_{0}),c_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\mathbb{Z}_{\geq 0})$ as input and returns a tuple
$(Z,p(Z))$, where $Z$ is an optimum solution to the following problem:

$\displaystyle\max$
$\displaystyle\left\\{p(Z)-b_{(G_{0},c_{0})}(Z)+y_{0}(Z)\mathrel{\mathop{\mathchar
58\relax}}S_{0}\subseteq Z\subseteq V-T_{0}\right\\}.$
(${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$)

  2. 2.

${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S_{0},T_{0},y_{0})$ returns a
tuple $(Z,p(Z))$, where $Z$ is an optimum solution to the following problem:

$\displaystyle\max$
$\displaystyle\left\\{p(Z)+y_{0}(Z)\mathrel{\mathop{\mathchar
58\relax}}S_{0}\subseteq Z\subseteq V-T_{0}\right\\}.$
(${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$)

The evaluation oracle for a function $p$ can be implemented using one query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$;
${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}$ can be implemented using one
query to ${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$
where the input hypergraph is the empty hypergraph. The next lemma from [7]
shows that ${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$
can be implemented using at most $|V|+1$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ where the
hypergraphs used as input to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ queries
have size of the order of the size of the hypergraph input to
${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$. We note
that the ${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$
as defined in [7] does not include the vector $y_{0}$ as an input parameter.
The proof of the next lemma follows by modifying the proof of the lemma from
[7] to incorporate the parameter $y_{0}$. We omit details here for brevity.

######  Lemma 2.2 (Lemma 2.2 of [7]).

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set
function, $(G=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$
be a hypergraph, and $S,T\subseteq V$ be disjoint sets. Then,
${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,w),S,T)$
can be implemented to run in $O(|V|(|V|+|E|))$ time using at most $|V|+1$
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,
each query to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ is on an
input hypergraph $(G_{0},c_{0})$ that has at most $|V|$ vertices and $|E|$
hyperedges.

##  3 Minimal Maximizers of Skew-Supermodular Function Sequences

In this section, we consider set families of maximizing sets of _skew-
supermodular_ functions. We state certain structural properties of these
families which we leverage in subsequent sections to show rapid convergence of
our algorithms.

For a function $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, a
set $X\subseteq V$ is a _$p$ -maximizer_ if $p(X)=K_{p}$. We let $\calF_{p}$
denote the family of _minimal_ $p$-maximizers. The following lemma says that
the family $\calF_{p}$ is disjoint if the function $p$ is skew-supermodular.
An important consequence of this lemma is that a transversal for the family
$\calF_{p}$ has polynomial (in particular, at most linear) size, a fact that
we will use in our analyzing the runtime of one of our algorithms in
subsequent sections.

######  Lemma 3.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function. Then, the family $\calF_{p}$ is a disjoint set-family.

The structural property of Lemma 3.1 is in fact a special case of a more
general structural property of certain sequences of skew-supermodular
functions. Let $p_{1},p_{2},\ldots,p_{\ell}$ be a sequence of skew-
supermodular functions defined over a ground set $V$. We will be interested in
the structure of the family of minimal maximizers across the entire sequence
of functions. In particular, we will focus on the family
$\calF_{p_{\leq\ell}}$, where the family $\calF_{p_{\leq i}}$ for $i\in[\ell]$
is defined as follows:

$\calF_{p_{\leq i}}\coloneqq\bigcup_{j\in[i]}\calF_{p_{i}}$

We note that for a general sequence of skew-supermodular functions, the sets
of the family $\calF_{p_{\leq\ell}}$ may not be well-structured. Consequently,
Lemma 3.1 applied to each function in the sequence implies that
$|\calF_{p_{\leq\ell}}|\leq O(\ell|V|)$. However, we will focus on a specific
structured sequence of skew-supermodular functions that will arise in the
analyses of all our algorithms in later sections. The next lemma shows that
for such a sequence, the family $\calF_{p_{\leq\ell}}$ is _laminar_ (which in
turn, will be helpful to conclude later that
$\left|\calF_{p_{\leq\ell}}\right|=O(|V|)$).

######  Lemma 3.2.

Let $\ell\in\Z_{+}$ be a positive integer. Let the sequence
$V_{1},V_{2},\ldots,V_{\ell}$ and
$\mathcal{Z}_{1},\mathcal{Z}_{2},\ldots,\mathcal{Z}_{\ell}$ be such that
$V_{i+1}\subseteq V_{i}$ and $\mathcal{Z}_{i}\coloneqq V_{i}-V_{i+1}$ for
$i\in[\ell-1]$. Let $g_{1},g_{2},\ldots,g_{\ell}$ be a sequence of non-
negative monotone submodular functions such that
$g_{i}\mathrel{\mathop{\mathchar 58\relax}}2^{V_{i}}\rightarrow\Z_{\geq 0}$
for each $i\in[\ell]$. Let $p_{1},p_{2},\ldots,p_{\ell}$ be a sequence of
functions such that $p_{i}\mathrel{\mathop{\mathchar
58\relax}}2^{V_{i}}\rightarrow\Z$ for $i\in[\ell]$, the function $p_{1}$ is
skew-supermodular, and $p_{i+1}\coloneqq{(p_{i}-g_{i})}/_{\mathcal{Z}_{i}}$
for each $i\in[\ell-1]$. Then, the family $\calF_{p_{\leq\ell}}$ is a laminar
family over the ground set $V_{1}$.

We prove Lemma 3.2 in Section B.1. For completeness, we also include a
simplified proof of the special case Lemma 3.1 in the same section.

##  4 Weak Cover with Linear Number of Hyperedges

In this section we prove Theorem 1.7. We restate it below.

See 1.7

We first describe our proof of Theorem 1.7 under the assumption that the input
function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$ is a
_positive_ function. In Section 4.1, we present our algorithm (see Algorithm
1). In Section 4.2, we show that our algorithm terminates within a finite
(pseudo-polynomial) number of recursive calls and returns a hypergraph
satisfying properties (1), (2) and (3) of Theorem 1.7 (see Lemma 4.4). In
Section 4.3, we give a tighter bound on the number of recursive calls
witnessed by our algorithm and show that the hypergraph returned by algorithm
also satisfies property (4) of Theorem 1.7 (see Lemma 4.9). Finally, in
Section 4.4, we show that our algorithm runs in strongly polynomial time,
given the appropriate function evaluation oracle (see Lemma 4.11). Lemmas 4.4,
4.9, and 4.11 together complete the proof of Theorem 1.7 under the assumption
that the input function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{+}$ is a _positive_ function.

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 and
${m}\backslash_{\mathcal{Z}}\mathrel{\mathop{\mathchar
58\relax}}V-\mathcal{Z}\rightarrow\Z_{+}$ is a _positive_ function satisfying
the two hypothesis conditions of Theorem 1.7, i.e.
${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}$. Furthermore, we
observe that a hypergraph satisfying properties (1)-(4) for the functions
${p}/_{\mathcal{Z}}$ and ${m}\backslash_{\mathcal{Z}}$ also satisfies the four
properties for the functions $p$ and $m$. 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.

###  4.1 The Algorithm

Our algorithm takes as input (1) a skew-supermodular function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$, and (2) a
_positive_ function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$
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 statement of
Theorem 1.7, the function $m$ that is input to our algorithm should be
positive.

We now give an informal description of the algorithm (refer to Algorithm 1 for
a formal description). Our algorithm is recursive. If $V=\emptyset$, then the
algorithm is in its base case and returns the empty hypergraph. Otherwise, the
algorithm is in its recursive case. First, the algorithm computes an arbitrary
minimal transversal $T\subseteq V$ for the family of $p$-maximizers – i.e., an
inclusionwise minimal set $T\subseteq V$ such that $T\cap X\neq\emptyset$ for
every $X\subseteq V$ with $p(X)=K_{p}$. Next, the algorithm computes the set
$\calD\coloneqq\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}m(u)=K_{p}\\}$
and defines the set $A\coloneqq T\cup\calD$. Next, the algorithm uses the set
$A$ to compute the following three intermediate quantities
$\alpha^{(1)},\alpha^{(2)},\alpha^{(3)}$:

  * •

$\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\\}$, and

  * •

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

and defines
$\alpha\coloneqq\min\left\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)}\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
recursively calls itself with the input tuple
$(p^{\prime\prime},m^{\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.

Algorithm 1 Weak covering with hyperedges

Input: Skew-supermodular 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\right)\mathrel{\mathop{\mathchar
58\relax}}$

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

2:else:

3: $\calD\coloneqq\\{u\in V\mathrel{\mathop{\mathchar 58\relax}}m(u)=K_{p}\\}$

4: $T\coloneqq$ an arbitrary minimal transversal for the family of
$p$-maximizers

5: $A\coloneqq T\cup\calD$

6:
$\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\\}\end{cases}$

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

8: Construct $\left(H_{0}\mathrel{\mathop{\mathchar
58\relax}}=\left(V,E_{0}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{A\right\\}\right),w_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\left\\{\alpha\right\\}\right)$

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

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

11:
$(H^{\prime\prime},w^{\prime\prime})\coloneqq\textsc{Algorithm}\left(p^{\prime\prime},m^{\prime\prime}\right)$

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

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

###  4.2 Termination and Partial Correctness

In this section, we show that Algorithm 1 terminates within a finite (pseudo-
polynomial) number of recursive calls, and moreover, returns a hypergraph
satisfying properties (1)-(3) of Theorem 1.7. The ideas in this section are
modifications of the results due to Szigeti [58]; we suggest first time
readers to skip this section and return to it as needed. Lemma 4.4 is the main
result of this section and is included at the end of the section. The next
lemma states useful properties of Algorithm 1.

######  Lemma 4.1.

Suppose that $V\not=\emptyset$ and 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$. Let
$\alpha,\mathcal{Z},m^{\prime\prime}$ be as defined by Algorithm 1. Then, we
have that

  1. (a)

$\alpha\geq 1$,

  2. (b)

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

  3. (c)

$m(X)\geq p(X)+\alpha|A\cap X|-\alpha$ for every $X\subseteq V$.

###### Proof.

We note that $K_{p}\geq m(u)\geq 1$ for every $u\in V$, where the final
inequality is because $m$ is a positive function, and consequently $K_{p}>0$
since $V\not=\emptyset$. We now prove each property separately below.

  1. (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)}\in\Z_{+}$. Our strategy to show this will be to
assume otherwise and arrive at a contradiction to the algorithm’s choice of
the set $A$.

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$. We note that $X\not=\emptyset$, since otherwise we have that
$0=\alpha^{(2)}=K_{p}-p(\emptyset)\geq K_{p}-m(\emptyset)=K_{p}>0$, a
contradiction. 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$, contradicting
that $A$ contains a transversal for the family of $p$-maximizers by Steps 4
and 5.

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$. Consequently, there exists a
vertex $v\in V$ that witnesses $\alpha^{(3)}=0$, i.e.
$\alpha^{(3)}=0=K_{p}-m(v)$ and $v\in V-A$, contradicting Steps 3 and 5.

  2. (b)

Let $m^{\prime},m^{\prime\prime},\mathcal{Z}$ be as defined by Algorithm 1. We
note that by Steps 4 and 5, the set $A$ contains a transversal for the family
of $p$-maximizers. If $\emptyset$ is the only $p$-maximizer, then we have that
$0<K_{p}=p(\emptyset)\leq m(\emptyset)=0$, a contradiction. Thus, there exists
a non-empty $p$-maximizer and consequently $A\not=\emptyset$. Moreover, by
part (a) of the current lemma, we have that $\alpha\geq 1$. Then, the
following shows the claim.

$m^{\prime\prime}(V-\mathcal{Z})={m^{\prime}}\backslash_{\mathcal{Z}}(V-\mathcal{Z})=m^{\prime}(V)=m(V)-\alpha\chi_{A}<m(V).$

  3. (c)

Let $X\subseteq V$ be arbitrary. We will show the claim by induction on $|X|$.
We first consider the base case $|X|=0$. Then, we have that $m(X)\geq
p(X)>p(X)-\alpha=p(X)+\alpha|A\cap X|-\alpha$, and so the claim holds.

Next, we consider the inductive case of $|X|\geq 1$. Let $T$ and $\calD$ be as
defined by Algorithm 1 for input tuple $(p,m)$. Let
$D\mathrel{\mathop{\mathchar 58\relax}}=\calD-T$ so that $A=T\uplus D$. We now
prove the claim by considering two cases. First, suppose that $D\cap
X\not=\emptyset$. Then, we have the following:

$\displaystyle m(X)$ $\displaystyle\geq m(A\cap X)$ $\displaystyle=m(T\cap
X)+m(D\cap X)$ $\displaystyle\geq\alpha|T\cap X|+K_{p}\cdot|D\cap X|$
$\displaystyle\geq K_{p}+\alpha|T\cap X|+\alpha(|D\cap X|-1)$
$\displaystyle\geq p(X)+\alpha|A\cap X|-\alpha.$

Here, the second inequality is because $m(u)\geq\alpha^{(1)}\geq\alpha$ for
each $u\in A$ by Step 6 and $m(u)=K_{p}$ for each $u\in D$. The third
inequality is because $K_{p}\geq m(u)\geq\alpha^{(1)}\geq\alpha$ for each
$u\in A$ by Step 6. The final inequality is because $K_{p}\geq p(X)$ and
$A=T\uplus D$.

Next, suppose that $D\cap X=\emptyset$. Suppose that $T\cap X=\emptyset$.
Then, we have that $A\cap X=\emptyset$ since $A=T\uplus D$. Consequently, we
have that $m(X)\geq p(X)>p(X)-\alpha=p(X)+\alpha|A\cap X|-\alpha,$ and hence,
the claim holds. Here, the first inequality is because $m(Z)\geq p(Z)$ for
every $Z\subseteq V$. We henceforth assume that $T\cap X\not=\emptyset$. Let
$y\in T\cap X$ be an arbitrary element. Since the set $T$ is a minimal
transversal of $p$-maximizers, there exists a $p$-maximizer $Y\subseteq V$
such that $T\cap Y=\\{y\\}$. In particular, we have that $|A\cap(X-Y)|=|A\cap
X|-1$. We now consider two cases based on the skew-supermodularity behavior of
the function $p$ at the sets $X$ and $Y$.

First, suppose that $p(X)+p(Y)\leq p(X\cap Y)+p(X\cup Y)$. Then, we have the
following:

$\displaystyle p(X)+p(Y)$ $\displaystyle\leq p(X\cap Y)+p(X\cup Y)$
$\displaystyle\leq p(X\cap Y)+p(Y)$ $\displaystyle\leq m(X\cap Y)+p(Y)$
$\displaystyle=m(X)-m(X-Y)+p(Y)$ $\displaystyle\leq m(X)-m(A\cap(X-Y))+p(Y)$
$\displaystyle\leq m(X)-\alpha|A\cap(X-Y)|+p(Y)$
$\displaystyle=m(X)-\alpha(|A\cap X|-1)+p(Y).$

Here, the second inequality is because the set $Y$ is a $p$-maximizer. The
third inequality is because $m(Z)\geq p(Z)$ for every $Z\subseteq V$. The
fourth inequality is because $m$ is a positive function. The fifth inequality
is because $m(u)\geq\alpha^{(1)}\geq\alpha$ for each $u\in A$ by Step 6. The
final equality is because $|A\cap(X-Y)|=|A\cap X|-1$. We note that rearranging
the terms gives us the claim.

Next, suppose that $p(X)+p(Y)\leq p(X-Y)+p(Y-X)$. Then, we have the following:

$\displaystyle p(X)+p(Y)$ $\displaystyle\leq p(X-Y)+p(Y-X)$ $\displaystyle\leq
p(X-Y)+p(Y)$ $\displaystyle\leq m(X-Y)-\alpha|A\cap(X-Y)|+\alpha+p(Y)$
$\displaystyle=m(X)-m(X\cap Y)-\alpha|A\cap(X-Y)|+\alpha+p(Y)$
$\displaystyle=m(X)-m(X\cap Y)-\alpha|A\cap X|+\alpha|A\cap X\cap
Y|+\alpha+p(Y)$ $\displaystyle\leq m(X)-\alpha|A\cap X|+\alpha+p(Y).$

Here, the second inequality is because the set $Y$ is a $p$-maximizer. The
third inequality is by the inductive hypothesis for the set $X-Y$: we note
that $|X-Y|<|X|$ since $y\in X\cap Y\not=\emptyset$. The final equality is
because $|A\cap(X-Y)|=|A\cap X|-|A\cap X\cap Y|$. The final inequality is
because $\alpha|A\cap X\cap Y|\leq m(A\cap X\cap Y)\leq m(X\cap Y)$ since
$m(u)\geq\alpha^{(1)}\geq\alpha$ for each $u\in A$ by Step 6.

∎

The next two lemmas will allow us to conclude that if the input functions $p$
and $m$ to a recursive call of Algorithm 1 satisfy conditions Theorem 1.7(a)
and (b), then the intermediate functions $p^{\prime},m^{\prime}$ and the input
functions to the subsequent recursive call $p^{\prime\prime},m^{\prime\prime}$
as constructed by Algorithm 1 also satisfy conditions Theorem 1.7(a) and (b).
Such recursive properties will be useful in inductively proving the
existential version of Theorem 1.7.

######  Lemma 4.2.

Suppose that $V\not=\emptyset$ and 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$. Let
$\alpha,p^{\prime},m^{\prime}$ be as defined by Algorithm 1. Then, we have
that

  1. (a)

The function $m^{\prime}\mathrel{\mathop{\mathchar
58\relax}}V\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 prove each property separately below.

  1. (a)

Let $u\in V$ be a vertex. If $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)}$.

  2. (b)

Let $X\subseteq V$ be a $p$-maximizer and $Y\subseteq V$ be a
$p^{\prime}$-maximizer. By Steps 4 and 5, the set $A$ is a transversal for the
family of $p$-maximizers, and consequently, $|A\cap X|\geq 1$. Thus,
$K_{p^{\prime}}=p^{\prime}(Y)\geq p^{\prime}(X)=p(X)-\alpha=K_{p}-\alpha$.
Here, the inequality is because $Y$ is a $p^{\prime}$-maximizer, and the
equality $p^{\prime}(X)=p(X)-\alpha$ is by the definition of the function
$p^{\prime}$ and because $|A\cap X|\geq 1$. 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

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

where the third equality is because $Y$ is a $p^{\prime}$-maximizer, the
fourth equality is because of $|A\cap Y|\geq 1$ and the definition of
$p^{\prime}$, 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

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

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

  3. (c)

First, consider a vertex $u\in A$. Then, we have that
$m^{\prime}(u)=m(u)-\alpha\leq K_{p}-\alpha=K_{p^{\prime}}$, where the
inequality is because $m(v)\leq K_{p}$ for every $v\in V$, and the final
equality is by part (b) of the current lemma. Next, consider a vertex $u\in
V-A$. Thus, $m^{\prime}(u)=m(u)$. In particular, we have that
$K_{p}-m^{\prime}(u)=K_{p}-m(u)\geq\alpha^{(3)}\geq\alpha$. 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 and let the hypergraph $(H_{0},w_{0})$ be as
defined in Step 8. First, suppose that $|X\cap A|=0$. Then, we have that
$b_{(H_{0},w_{0}))}(X)=0$, and consequently $m^{\prime}(X)=m(X)\geq
p(X)=p^{\prime}(X)$. Thus, the claim holds. Next, 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(Z)-b_{(H_{0},w_{0})}(X)=p^{\prime}(X).$

Here, the inequality holds by Lemma 4.1(c). The final equality is because
$|X\cap A|\geq 1$.

∎

######  Lemma 4.3.

Suppose that $V\not=\emptyset$ and 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$. Let
$\alpha,\mathcal{Z},p^{\prime\prime},m^{\prime\prime}$ be as defined by
Algorithm 1. Then, we have that

  1. (a)

$p^{\prime\prime}={(p-b_{(H_{0},w_{0})})}/_{\mathcal{Z}}$; moreover, the
function $p^{\prime\prime}$ is skew-supermodular,

  2. (b)

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

  3. (c)

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

  4. (d)

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

  5. (e)

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

###### Proof.

We prove each property separately below.

  1. (a)

We note that $p^{\prime\prime}={(p-b_{(H_{0},w_{0})})}/_{\mathcal{Z}}$ by Step
10. Moreover, the function $p^{\prime\prime}$ is skew-supermodular because
$b_{(H_{0},w_{0})}$ is submodular and function contraction is known to
preserve skew-supermodularity (see Proposition 4 of [58]).

  2. (b)

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

  3. (c)

By Lemma 4.2(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.

  4. (d)

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 4.2(a) and the final equality is by Lemma
4.2(b) and part (c) of the current lemma.

  5. (e)

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 4.2(a).

∎

We conclude the section with the main result of the section.

######  Lemma 4.4.

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 terminates within a finite (pseudo-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 1 satisfies the
following three 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$, and

  3. 3.

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

###### 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 1 is
in its base case (Step 1) and terminates. Moreover, Step 1 returns an empty
hypergraph which satisfies properties (1)-(3) and so the lemma holds.

For the inductive case, suppose that $\phi(m)>0$. Since $m$ is a positive
function, we have that $V\not=\emptyset$ and so Algorithm 2 is in its
recursive case. Thus, by Lemma 4.3(a), (b), (d) and (e), the tuple
$(p^{\prime\prime},m^{\prime\prime})$ constructed by Algorithm 1 satisfy the
hypothesis of the current lemma. We note that the tuple
$(p^{\prime\prime},m^{\prime\prime})$ is the input to the subsequent recursive
call of Algorithm 1 by Step 11. Moreover, $\phi(m^{\prime\prime})<\phi(m)$ by
Lemma 4.1(b). Thus, by induction, the subsequent recursive call to Algorithm 1
terminates and returns a hypergraph
$(H^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime}),w^{\prime\prime})$
satisfying properties (1)-(3) for the tuple
$(p^{\prime\prime},m^{\prime\prime})$. Consequently, the entire execution of
Algorithm 1 terminates within a finite number of recursive calls. Let
$(H=(V,E),w)$ be the hypergraph returned by Step 11 and let
$(H_{0},w_{0}),\mathcal{Z},A,\alpha$ be as defined by Algorithm 1 for the
input tuple $(p,m)$. 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 10. 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 4.3(c). ∎

###  4.3 Recursion Depth and Hypergraph Support Size

In this section, we give an upper bound on the number of recursive calls
witnessed by an execution of Algorithm 1. The main result of this section is
Lemma 4.9 which we show at the end of the section. We begin with some
convenient notation that will be used in this section as well as the next
section.

##### Notation.

By Lemma 4.4, the number of recursive calls made by Algorithm 1 is finite. We
will use $\ell$ to denote the depth of recursion. We will refer to the
recursive call at depth $i\in[\ell]$ as _recursive call $i$_ or the _$i^{th}$
recursive call_. We 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$ and $m_{i}\mathrel{\mathop{\mathchar
58\relax}}V_{i}\rightarrow\Z_{\geq 0}$ denote the input functions to recursive
call $i$. Furthermore, we let
$\calD_{i},T_{i},A_{i},\alpha_{i},\alpha_{i}^{(1)},\alpha_{i}^{(2)},\alpha_{i}^{(3)},\mathcal{Z}_{i},(H^{i}_{0},w^{i}_{0}),p^{\prime}_{i},m^{\prime}_{i},p^{\prime\prime}_{i},m^{\prime\prime}_{i}$
denote the quantities
$\calD,T,A,\alpha,\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\mathcal{Z},(H_{0},w_{0}),$
$p^{\prime},m^{\prime},p^{\prime\prime},m^{\prime\prime}$ as defined by
Algorithm 1 during the $i^{th}$ recursive call for $i\in[\ell-1]$. For
convenience, we also define the relevant sets, values and functions during the
base case ($\ell^{th}$ recursive call) as follows:
$A_{\ell},\calD_{\ell},\mathcal{Z}_{\ell}\mathrel{\mathop{\mathchar
58\relax}}=\emptyset$,
$\alpha_{\ell},\alpha_{\ell}^{(1)},\alpha_{\ell}^{(2)},\alpha_{\ell}^{(3)}\mathrel{\mathop{\mathchar
58\relax}}=0$,
$m_{\ell}^{\prime},m_{\ell}^{\prime\prime},m_{\ell+1}\mathrel{\mathop{\mathchar
58\relax}}=m_{\ell}$, and
$p_{\ell}^{\prime},p_{\ell}^{\prime\prime},p_{\ell+1}\mathrel{\mathop{\mathchar
58\relax}}=p_{\ell}$. Finally, let
$\left(H_{i}=\left(V_{i},E_{i}\right),w_{i}\right)$ denote the hypergraph
returned by the $i^{th}$ recursive call.

We note that Lemma 4.3 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})$ satisfies the hypothesis of Theorem 1.7.

######  Lemma 4.5.

Suppose that 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 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]$ we have that
$p_{i}\mathrel{\mathop{\mathchar 58\relax}}2^{V_{i}}\rightarrow\Z$ is a skew-
supermodular function and $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 all $X\subseteq V_{i}$ and $m_{i}(u)\leq
K_{p_{i}}$ for all $u\in V_{i}$.

##### Set Families.

For our analysis, we will focus on certain set families associated with an
execution of Algorithm 1. Let $i\in[\ell]$ be a recursive call of Algorithm 1.
We define $\calZ_{\leq i}\coloneqq\cup_{j\in[i]}\mathcal{Z}_{i}$. We use
$\calF_{i}$ and $\calF_{i}^{\prime}$ to denote the families of _minimal_
$p_{i}$-maximizers and $p_{i}^{\prime}$-maximizers respectively, i.e.,
$\calF_{i}$ is the collection of inclusionwise minimal sets in the family
$\\{X\subseteq V_{i}\mathrel{\mathop{\mathchar
58\relax}}p_{i}(X)=K_{p_{i}}\\}$ and $\calF_{i}^{\prime}$ is the collection of
inclusionwise minimal sets in the family $\\{X\subseteq
V_{i}\mathrel{\mathop{\mathchar
58\relax}}p_{i}^{\prime}(X)=K_{p_{i}^{\prime}}\\}$. Lemma 4.6 below shows the
progression of these families across recursive calls of an execution of
Algorithm 1. 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 4.7 below summarizes useful
properties of the stated families.

######  Lemma 4.6.

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]$, 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.

We note that both properties trivially hold if $i=\ell$, and so we consider
the case where when $i\leq\ell-1$ (i.e. Algorithm 1 is in its recursive case).
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
both parts separately below.

  1. (a)

Let $Y\subseteq V_{i}$ be a $p_{i}$-maximizer. We recall that by Steps 4 and 5
during the $i^{th}$ recursive call, 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^{\prime}_{i}}$,
where the first equality is because $A_{i}\cap Y\not=\emptyset$ and the third
equality is by Lemma 4.5 and Lemma 4.2(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