problem[1]

#1

# Hypergraph Splitting-off and Covering Skew-Supermodular Functions in
Strongly Polynomial Time

Kristóf Bérczi MTA-ELTE Matroid Optimization Research Group and ELKH-ELTE
Egerváry Research Group, Department of Operations Research, 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 satisfying certain properties. In graph network design problems,
the number of edges in an arbitrary solution is at most the square of the
number of vertices. In contrast, in hypergraph network design problems, the
number of hyperedges in an arbitrary solution could be exponential in the
number of vertices and hence, additional care is necessary to design
polynomial-time algorithms. The central theme of this work is to show that
certain hypergraph network design problems admit solutions with polynomial
number of hyperedges 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 algorithms that return (near-)uniform
hypergraphs as solutions. The hypergraph network design problems that we focus
upon are splitting-off operation in hypergraphs, connectivity augmentation
using hyperedges, and covering skew-supermodular functions using hyperedges.
Our definition of the splitting-off operation in hypergraphs and our proof
showing the existence of the operation using a strongly polynomial-time
algorithm to compute it are likely to be of independent graph-theoretical
interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Application of Algorithmic Weak to Strong Cover by Merging: Hypergraph Splitting Off
    3. 1.3 Proof Techniques
      1. 1.3.1 Weak to Strong cover by Merging
      2. 1.3.2 Degree-specified simultaneous skew-supermodular weak cover using near-uniform hyperedges
    4. 1.4 Related Work
  2. 2 Preliminaries
  3. 3 Weak to Strong Cover in Strongly Polynomial Time
    1. 3.1 Weak to Strong Cover Algorithm
    2. 3.2 Properties of Tight Sets
    3. 3.3 Termination and Partial Correctness of Algorithm 1
    4. 3.4 Number of Recursive Calls and Hypergraph Support Size
    5. 3.5 Run-time of Algorithm 1
  4. 4 Weak Cover in Strongly Polynomial Time
    1. 4.1 The Algorithm
    2. 4.2 Termination and Partial Correctness of Algorithm 2
    3. 4.3 Number of Recursive Calls of Algorithm 2 with $\alpha\in\\{\alpha^{(1)},\alpha^{(2)},\alpha^{(3)},\alpha^{(5)}\\}$
    4. 4.4 Feasibility of Execution for Skew-supermodular Functions
    5. 4.5 Run-time for Skew-supermodular Functions
    6. 4.6 Properties of Skew-Supermodular Functions
  5. 5 Weak Cover of One Function with Linear Number of Near-Uniform Hyperedges
    1. 5.1 Laminarity of Projected Maximal Tight Sets Across Recursive Calls
    2. 5.2 Adding Good Hyperedges
    3. 5.3 Number of Recursive Calls and Hypergraph Support Size
  6. 6 Weak Cover of Two Functions with Quadratic Number of Near-Uniform Hyperedges
    1. 6.1 Slack and Pairwise Slack Functions
    2. 6.2 Number of Recursive Calls and Hypergraph Support Size
  7. 7 Applications of Algorithmic Weak Cover
    1. 7.1 Strong cover to weak cover reduction for symmetric skew-supermodular functions
    2. 7.2 Hypergraph local connectivity augmentation using hyperedges
    3. 7.3 Hypergraph node-to-area connectivity augmentation using hyperedges
    4. 7.4 Degree-constrained mixed-hypergraph global connectivity augmentation using hyperedges
  8. 8 Conclusion
  9. A Maximization oracles for functions arising in applications
  10. B An Example for Weak To Strong Cover with Quadratic New Hyperedges
  11. C Properties of Laminar Families and Skew-Supermodular Functions
    1. C.1 Projection of Laminar Family
    2. C.2 Minimal Maximizers
    3. C.3 Cumulative Minimal Maximizer Family Across Function Sequences
    4. C.4 Tight Sets
  12. D Optimization Problems using Function Maximization Oracle
    1. D.1 ${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$ using ${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$
    2. D.2 Computing the Family of Minimal $p$-Maximizers
    3. D.3 Computing the Family of Maximal $(p,H,w)$-Tight Sets
    4. D.4 Optimizing over $Q$-polyhedron in Strongly Polynomial Time
    5. D.5 Computing $\alpha^{(4)}$: Ratio Maximization Oracle in Strongly Polynomial Time

##  1 Introduction

A hypergraph $H=(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$. We will
denote a hypergraph $H=(V,E)$ with hyperedge weights
$w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+}$ by the tuple
$(H,w)$ and use $H_{w}$ to denote the unweighted multi-hypergraph over vertex
set $V$ containing $w(e)$ copies of every hyperedge $e\in E$. 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 the
same size, then the hypergraph is said to be _uniform_ and if every pair of
hyperedges differ in size by at most one, then the hypergraph is said to be
_near-uniform_. We will call hyperedges of size one as _singleton hyperedges_.
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 note that every graph is a
near-uniform hypergraph (but not necessarily a uniform hypergraph).
Hypergraphs offer a richer and more accurate model than graphs for several
applications. Consequently, hypergraphs have found applications in several
modern areas (e.g., see [66, 58, 46, 56]) and these applications have, in
turn, driven exciting recent progress in algorithms for hypergraph
optimization problems [42, 29, 14, 16, 13, 17, 63, 3, 41, 40, 45, 38, 57].

We note that 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, one needs to be mindful of the number of hyperedges
in the hypergraph returned by the algorithm. Recent works have explored this
issue in the context of hypergraph sparsifiers [42, 16, 63, 3, 17, 41, 40, 45,
38, 57] and shown that every hypergraph (possibly with exponential number of
hyperedges) admits a cut/coverage/spectral sparsifier in which the number of
hyperedges is near-linear in the number of vertices and such a sparsifier can
be constructed in time near-linear in the size of the input hypergraph. The
central theme of this work is to show that certain hypergraph network design
problems admit solutions with _polynomial_ number of hyperedges and can be
solved in _strongly polynomial time_. The previous fastest run-time known for
these problems was psuedo-polynomial. Furthermore, we focus on obtaining
solutions where the hypergraph is required to be uniform/near-uniform in
addition to satisfying other network design constraints. Uniformity (or near-
uniformity) is a natural constraint while designing 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. The hypergraph network design problems
that we focus upon are the splitting-off operation in hypergraphs, degree-
specified hypergraph connectivity augmentation using hyperedges, and their
generalization – namely covering skew-supermodular functions using hyperedges.
Before describing these hypergraph network design problems, we set up some
necessary notation.

##### Notation.

Let $(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ be a
hypergraph. For $X\subseteq V$, let $\delta_{H}(X)\coloneqq\\{e\in
E\mathrel{\mathop{\mathchar 58\relax}}e\cap X\neq\emptyset,e\setminus
X\neq\emptyset\\}$ and $B_{H}(X)\coloneqq\\{e\in E\mathrel{\mathop{\mathchar
58\relax}}e\cap X\neq\emptyset\\}$. We define the cut function
$d_{(H,w)}\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z_{\geq 0}$
and the coverage function $b_{(H,w)}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z_{\geq 0}$ by
$d_{(H,w)}(X)\coloneqq\sum_{e\in\delta_{H}(X)}w(e)$ and
$b_{(H,w)}(X)\coloneqq\sum_{e\in B_{H}(X)}w(e)$ for every $X\subseteq V$. For
a vertex $u\in V$, we use $b_{(H,w)}(u)$ to denote $b_{(H,w)}(\\{u\\})$. We
define the _degree_ of a vertex $u\in V$ to be $b_{(H,w)}(u)$ (as opposed to
$d_{(H,w)}(\\{u\\})$ since a hypergraph could have singleton hyperedges). For
distinct vertices $u,v\in V$, let
$\lambda_{(H,w)}(u,v)\coloneqq\min\\{d_{(H,w)}(X)\mathrel{\mathop{\mathchar
58\relax}}u\in X\subseteq V\setminus\\{v\\}\\}$ – i.e., $\lambda_{(H,w)}(u,v)$
is the value of a minimum $\\{u,v\\}$-cut in the hypergraph (by Menger’s
theorem, $\lambda_{(H,w)}(u,v)$ is the $u-v$ hyperedge-connectivity). 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)$. For a
function $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\R$, we denote
$m(X)\coloneqq\sum_{u\in X}m(u)$.

##### Splitting-off operation.

The splitting-off operation in graphs is a simple yet powerful operation in
graph theory. It is a reduction operation that detaches all edges incident to
a given vertex and adds new edges between the neighbors of that vertex while
preserving their degrees and edge connectivity. Equivalently, it enables a
vertex to exit the network by informing its neighbors how to reconfigure the
lost links among themselves in order to preserve edge connectivity. Lovász
showed the existence of the splitting-off operation to preserve global edge
connectivity in graphs (Exercise 6.53 in [48]) and Mader showed the existence
of the splitting-off operation to preserve all pairwise edge connectivities in
graphs under mild conditions [49]. Owing to the inductive nature of the
splitting-off operation, it enables fundamental graph theoretical results as
well as efficient algorithms and min-max relations for numerous graph
optimization problems – it has been applied to address edge connectivity
augmentation [21, 23, 1, 24, 52], orientation [25], network design [30, 39,
12], tree packing [7, 43], to enumerate approximate minimum cuts [53, 33, 31],
and to characterize $k$-edge-connected graphs [24]. In this work, we formalize
a notion of the splitting-off operation in hypergraphs, show its existence,
and develop the first strongly polynomial-time algorithm to implement it (see
Section 1.2). We believe that our definition of the splitting-off operation in
hypergraphs as well as our results showing the existence of the operation and
efficient algorithms to compute it are likely to find future applications akin
to the splitting-off operation in graphs.

##### Degree-specified Connectivity Augmentation.

It is well-known that the splitting-off operation to preserve connectivity in
graphs is a special case of the degree-specified graph connectivity
augmentation using edges problem. In the degree-specified graph connectivity
augmentation using edges problem, the input is a degree requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$, 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_{\geq 0}$.
The goal is to verify if there exists a graph
$(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 one. We emphasize that degree-
specified graph connectivity augmentation using edges problem is a feasibility
problem and not an optimization problem111The degree-specified graph
connectivity augmentation using edges problem should not be confused with the
min-cost connectivity augmentation problem where the input consists of costs
on the edges of a complete graph, a graph $G=(V,E)$, and a target connectivity
function $r\mathrel{\mathop{\mathchar
58\relax}}\binom{V}{2}\rightarrow\Z_{\geq 0}$, and the goal is to find a
minimum cost set of edges to add to $G$ so that the resulting graph
$G^{\prime}$ is such that $\lambda_{G^{\prime}}(u,v)\geq r(\\{u,v\\})$ for
every distinct $u,v\in V$. We note that min-cost connectivity augmentation
problem is NP-hard.. It is solvable in polynomial time [67, 8, 23, 21] and
designing fast algorithms for it has been an active area of research [27, 7,
54, 4, 44] with exciting progress in the last couple of years [10, 11, 9].

The polynomial-time solvability of the degree-specified graph connectivity
augmentation using edges problem naturally raises the degree-specified
hypergraph connectivity augmentation using hyperedges problem. The input here
is a hypergraph $(G=(V,E_{G}),c_{G}\mathrel{\mathop{\mathchar
58\relax}}E\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 a hypergraph $(H=(V,E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E\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 one. We note that membership of the
degree-specified hypergraph connectivity augmentation using hyperedges problem
in NP is not obvious – 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. Szigeti [64] gave a
characterization for the existence of a feasible solution. His proof technique
also implies that if there exists a feasible hypergraph $(H,w_{H})$, then
there exists a feasible hypergraph with at most
$\min\\{2^{|V|},\max\\{r(\\{u,v\\})\mathrel{\mathop{\mathchar
58\relax}}\\{u,v\\}\in\binom{V}{2}\\}\\}$ hyperedges (i.e., if the target
connectivity function is given in unary, then there exists a solution
$(H,w_{H})$ in which the number of hyperedges is polynomial in the size of the
input). In this work, we show that for a feasible instance of the degree-
specified hypergraph connectivity augmentation using hyperedges problem, there
exists a solution $(H,w_{H})$ such that the number of hyperedges in $H$ is
linear in the number of vertices (irrespective of the values of the target
connectivity function and the degree requirement function). Moreover, we show
that such a solution $(H,w_{H})$ can be found in strongly polynomial time. We
will discuss these details in Section 7.2.

We emphasize that the splitting-off operation to preserve connectivity in
hypergraphs that we define in Section 1.2 is not a special case of the degree-
specified hypergraph connectivity augmentation using hyperedges problem (in
contrast to graphs). We clarify this difference in Section 1.2. Owing to this
difference, we have to study these two hypergraph network design problems
independently. Nevertheless, a notion of skew-supermodular cover using
hyperedges provides a common framework to study both these problems.

##### Skew-Supermodular Cover using Hyperedges.

A generalization of degree-specified hypergraph connectivity augmentation
using hyperedges problem has been proposed and studied in the literature. The
generalization encompasses several applications in connectivity augmentation
and beyond, so we focus on this generalization. We recall certain definitions
before describing the generalization.

######  Definition 1.1.

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

  1. 1.

The set function $p$

    1. (a)

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

    2. (b)

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

      1. i.

$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. ii.

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

  2. 2.

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

  3. 3.

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

We will consider the following two variants of degree-specified skew-
supermodular cover problems (we will define
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ shortly):

Degree-specified skew-supermodular weak cover using hyperedges problem. 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.

Degree-specified symmetric skew-supermodular strong cover using hyperedges
problem. 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.

In the above problems, if we additionally require that the hypergraph $(H,w)$
is _near-uniform_ , then we denote the problems as degree-specified skew-
supermodular weak cover using _near-uniform_ hyperedges and degree-specified
symmetric skew-supermodular strong cover using _near-uniform_ hyperedges,
respectively.

We emphasize a difference between the above two problems. In the degree-
specified skew-supermodular _weak_ cover using hyperedges problem, if we drop
the requirement that $\sum_{e\in E}w(e)=K_{p}$ from the problem definition,
then the resulting problem admits a trivial feasible solution if the instance
is feasible222Consider the hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$, where
$E\coloneqq\\{\\{u\\}\mathrel{\mathop{\mathchar 58\relax}}u\in V,\ m(u)\geq
1\\}$ with $w(\\{u\\})\coloneqq m(u)$ for every $\\{u\\}\in E$.. Imposing this
requirement makes the problem non-trivial and leads to connections to the
symmetric skew-supermodular strong cover problem (we will discuss the
connections in Section 7.1). In contrast, we do not impose the same
requirement in the degree-specified _symmetric_ skew-supermodular _strong_
cover using hyperedges problem. We note that the degree-specified hypergraph
connectivity augmentation using hyperedges problem is a special case of the
degree-specified symmetric skew-supermodular strong cover using hyperedges
problem333Consider the same degree requirement function and the set function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ defined by
$p(X)\coloneqq\max\\{r(\\{u,v\\})\mathrel{\mathop{\mathchar 58\relax}}u\in
X,v\in V-X\\}-d_{(G,c)}(X)$ for every $X\subseteq V$, which is symmetric skew-
supermodular..

In order to design algorithms for degree-specified skew-supermodular cover
using hyperedges problems with run-time that is polynomial in the size of the
ground set $V$, we will need access to the input skew-supermodular function
$p$ in a suitable fashion. Bernáth and Király [5] showed that it is impossible
to solve either problem mentioned above using polynomial number of queries to
the evaluation oracle444For 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)$. of the function $p$. Moreover, it
is impossible to solve skew-supermodular maximization (i.e.,
$\max\\{p(X)\mathrel{\mathop{\mathchar 58\relax}}X\subseteq V\\}$ for a skew-
supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$) using polynomial number of queries to the
function evaluation oracle [32]. To overcome these barriers, Bernáth and
Király [5] suggested access to a certain function maximization oracle that we
describe below.

######  Definition 1.2.

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},w_{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}_{\geq 0})$, disjoint sets
$S_{0},T_{0}\subseteq V$, and a vector ${y_{0}}\in\R^{V}$, and 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}$)

For all known applications, the above-mentioned function maximization oracle
can be implemented to run in strongly polynomial time. We will discuss these
applications, the associated oracles, and the implications of our results to
these applications in Sections 1.2 and 7. We emphasize that in all our
algorithmic results, the run-time will include the time to construct the
hypergraphs that are used as inputs to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.

##### Weak to Strong Cover by Merging.

If a hypergraph $(H,w)$ 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 cover555For 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 [5] showed that a weak cover of a _symmetric_ skew-supermodular
function can be converted to a strong cover of the same function by repeated
_merging of disjoint hyperedges_. We recall their definition of the merging
operation, discuss their result, and its significance now.

######  Definition 1.3.

Let $(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ be a
hypergraph with $H_{w}$ being the associated multi-hypergraph. By _merging two
disjoint hyperedges_ of $H_{w}$, we refer to the operation of replacing them
by their union in $H_{w}$. We will say that a hypergraph
$(G=(V,E_{G}),c\mathrel{\mathop{\mathchar 58\relax}}E_{G}\rightarrow\Z_{+})$
is obtained from $(H,w)$ by _merging hyperedges_ if the multi-hypergraph
$G_{c}$ is obtained from the multi-hypergraph $H_{w}$ by repeatedly merging
two disjoint hyperedges.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a symmetric
skew-supermodular function and $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ be a hypergraph. Bernáth and Király showed that
if $(H,w)$ weakly covers $p$, then there exists a hypergraph
$(G=(V,E_{G}),c\mathrel{\mathop{\mathchar 58\relax}}E_{G}\rightarrow\Z_{+})$
obtained from $(H,w)$ by merging hyperedges such that $(G,c)$ strongly covers
$p$. Their result is significant for two reasons: firstly, they observed that
their result helps in reducing the degree-specified symmetric skew-
supermodular _strong_ cover using hyperedges problem to the degree-specified
symmetric skew-supermodular _weak_ cover using hyperedges problem (we will
discuss this reduction in Section 7.1). Secondly, we observe that their
merging operation can be interpreted as the splitting-off operation in
hypergraphs (we will discuss this interpretation in Section 1.2). This
interpretation is one of the contributions of our work.

Motivated by the splitting-off interpretation of Bernáth and Király’s result,
we consider the algorithmic question related to their result, i.e., given a
weak cover $(H=(V,E_{H}),w\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ of a symmetric skew-supermodular function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ that is given via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, can we
construct a strong cover $(G=(V,E_{G}),c\mathrel{\mathop{\mathchar
58\relax}}E_{G}\rightarrow\Z_{+})$ of $p$ by merging hyperedges of $(H,w)$ in
polynomial time?

Weak to Strong Cover by Merging problem. Given: A hypergraph
$(H=(V,E_{H}),w\mathrel{\mathop{\mathchar 58\relax}}E_{H}\rightarrow\Z_{+})$
and a symmetric skew-supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ such that
$(H,w)$ weakly covers $p$. Goal: Construct a hypergraph
$(G=(V,E_{G}),c\mathrel{\mathop{\mathchar 58\relax}}E_{G}\rightarrow\Z_{+})$
such that $(G,c)$ strongly covers the function $p$, and $(G,c)$ is obtained
from $(H,w)$ by merging hyperedges.

Bernáth and Király’s proof is in fact algorithmic, but the run-time of the
associated algorithm is not shown to be polynomial. Their proof implies that
the number of additional hyperedges in the hypergraph $(G,c)$ returned by
their algorithm is at most $\sum_{e\in E}w(e)$ (i.e.,
$|E_{G}|-|E_{H}|\leq\sum_{e\in E}w(e)$) and the run-time of the algorithm is
$O(\sum_{e\in E_{H}}(|e|+w(e))$. In particular, their run-time is polynomial
only if the input weights are given in unary. Our first result (Theorem 1.1)
shows that there exists a hypergraph $(G,c)$ obtained from $(H,w)$ by merging
hyperedges such that $(G,c)$ strongly covers $p$ and the number of additional
hyperedges in $G$ compared to $H$ is $O(|V|)$ (i.e.,
$|E_{G}|-|E_{H}|=O(|V|)$); moreover, our proof is constructive and leads to a
strongly polynomial-time algorithm to find such a strong cover $(G,c)$ of $p$
assuming access to the function $p$ via
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. This
result leads to a strongly polynomial-time algorithm for hypergraph splitting-
off (see Section 1.2).

As mentioned above, the weak to strong cover by merging result allows one to
focus on degree-specified (symmetric) skew-supermodular weak cover using
hyperedges problem (as opposed to the strong cover using hyperedges problem).
We now discuss the status and our results for weak cover using hyperedges.

##### Degree-specified skew-supermodular weak cover using hyperedges.

For degree-specified skew-supermodular weak cover using hyperedges problem,
Szigeti [64] showed a complete characterization for the existence of a
feasible solution. Let $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z_{\geq 0}$ be a degree requirement function and
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function. Szigeti showed that 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}$ 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$. Furthermore, Szigeti
showed that if $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$
for every $u\in V$, then 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}$ can
be found in time $O(K_{p})$. This leads to the natural question of whether
such a hypergraph can be found in _strongly polynomial time_ which is the main
focus of our work. We note that the number of hyperedges in the hypergraph
returned by Szigeti’s algorithm is at most $K_{p}$ (since $\sum_{e\in
E}w(e)=K_{p}$ and $w(e)\geq 1$ for every $e\in E$), but $K_{p}$ is not
necessarily polynomial in the input size. Our second result (Theorem 1.2)
improves the number of hyperedges in the previous statement to linear in the
number of vertices (in particular, independent of $K_{p}$) and shows a
strongly polynomial-time algorithm to solve the degree-specified skew-
supermodular weak cover using hyperedges problem.

##### Degree-specified skew-supermodular weak cover using near-uniform
hyperedges.

Subsequent to Szigeti’s work, Bernáth and Király [5] developed an LP-based
approach to solve the degree-specified skew-supermodular weak cover using
hyperedges problem. Their LP-based approach allowed them to address the
degree-specified skew-supermodular weak cover using _near-uniform_ hyperedges
problem. Let $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq 0}$
be a degree requirement function and $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ be a skew-supermodular function. For the
instance $(m,p)$ of degree-specified skew-supermodular weak cover using _near-
uniform_ hyperedges problem to have a feasible solution, it is clear that the
conditions $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for
every $u\in V$ are necessary. Bernáth and Király showed that these conditions
are also sufficient. Furthermore, they showed that if $m(X)\geq p(X)$ for
every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$, then a _near-
uniform_ 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 $p$, and $\sum_{e\in E}w(e)=K_{p}$ can be found in
time $O(K_{p})$. We note that the number of hyperedges in the hypergraph
returned by their algorithm is at most $K_{p}$ (since $\sum_{e\in
E}w(e)=K_{p}$ and $w(e)\geq 1$ for every $e\in E$). Our second result (Theorem
1.2) improves the number of hyperedges in the previous statement to linear in
the number of vertices (in particular, independent of $K_{p}$) and shows a
strongly polynomial-time algorithm to solve the degree-specified skew-
supermodular weak cover using near-uniform hyperedges problem.

##### Degree-specified simultaneous skew-supermodular weak cover using (near-
uniform) hyperedges.

Bernáth and Király’s LP-based approach also addressed a simultaneous variant
of degree-specified skew-supermodular weak cover using near-uniform
hyperedges. We describe this variant now.

Degree-specified simultaneous skew-supermodular weak cover using hyperedges
problem. 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.

In the above problem, if we additionally require that the hypergraph $(H,w)$
is _near-uniform_ , then we denote the problem as degree-specified
simultaneous skew-supermodular weak cover using _near-uniform_ hyperedges.

Let $(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)$ be an instance of
the degree-specified simultaneous skew-supermodular weak cover using
hyperedges problem. Consider the function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ defined by $p(X)\coloneqq\max\\{q(X),r(X)\\}$
for every $X\subseteq V$. We note that this function $p$ is not skew-
supermodular. For the instance $(m,q,r)$ to be feasible, it is clear that the
conditions $m(X)\geq p(X)$ for every $X\subseteq V$ and $m(u)\leq K_{p}$ for
every $u\in V$ are necessary (via Szigeti’s characterization for the existence
of a feasible solution for degree-specified skew-supermodular weak cover using
hyperedges problem). Bernáth and Király [5] showed that this condition is also
sufficient using their LP-based approach. They showed that if $m(X)\geq p(X)$
for every $X\subseteq V$ and $m(u)\leq K_{p}$ for every $u\in V$, then there
exists a _near-uniform_ 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$, $\sum_{e\in
E}w(e)=\max\\{K_{q},K_{r}\\}$, and moreover, such a near-uniform hypergraph
$(H,w)$ can be found in time $O(K_{p})$. We note that the number of hyperedges
in the hypergraph returned by their algorithm is at most $K_{p}$ (since
$\sum_{e\in E}w(e)=K_{p}$ and $w(e)\geq 1$ for every $e\in E$). An application
of this result is that it strengthens Schrijver’s supermodular coloring
theorem [59] and leads to a strongly polynomial-time algorithm for the
strengthened supermodular coloring theorem since $K_{p}\leq|V|$ in that
application666We avoid discussing the details of the supermodular coloring
theorem since Bernáth and Király’s results already led to a strongly
polynomial-time algorithm for the supermodular coloring theorem and our
results do not imply anything new for this application. We refer readers
interested in the supermodular coloring theorem and its applications to [59,
60, 64, 5, 36, 51].. We will discuss other applications of this result where
$K_{p}$ is not necessarily polynomial in the size of the ground set $V$ in
Section 7. Our third result (Theorem 1.3) improves on the number of hyperedges
in the result of Bernáth and Király to quadratic in the number of vertices (in
particular, independent of $K_{p}$) and shows a strongly polynomial-time
algorithm to solve the degree-specified simultaneous skew-supermodular weak
cover using (near-uniform) hyperedges problem.

###  1.1 Our Results

We formally state our results in this section. We refer the reader to Table 1
for a summary of our results in comparison to previously known results.

##### Weak to Strong Cover by Merging in Strongly Polynomial Time.

As our first result, we show that given a hypergraph $(H,w)$ that _weakly_
covers a symmetric skew-supermodular function, there exists a hypergraph
$(H^{*},w^{*})$ that _strongly_ covers the same function such that
$(H^{*},w^{*})$ is obtained from $(H,w)$ by merging hyperedges and the number
of additional hyperedges in $(H^{*},w^{*})$ compared to $(H,w)$ is $O(|V|)$;
moreover, such a hypergraph $(H^{*},w^{*})$ can be obtained in strongly
polynomial time using polynomial number of calls to the function maximization
oracle.

######  Theorem 1.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a symmetric
skew-supermodular function. Let $\left(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ be a hypergraph such that
$b_{(H,w)}(X)\geq p(X)$ for every $X\subseteq V$. Then, there exists a
hypergraph $\left(H^{*}=(V,E^{*}),w^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+}\right)$ such that

  1. $(1)$

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

  2. $(2)$

the hypergraph $(H^{*},w^{*})$ is obtained by merging hyperedges of the
hypergraph $(H,w)$, and

  3. $(3)$

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

Furthermore, given a hypergraph $(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ and access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ of a
symmetric skew-supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ where $b_{(H,w)}(X)\geq p(X)$ for every
$X\subseteq V$, there exists an algorithm that runs in time $\poly(|V|,|E|)$
using $\poly(|V|)$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ to return
a hypergraph $\left(H^{*}=(V,E^{*}),w^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+}\right)$ satisfying the above three
properties.

We emphasize that the run-time above includes the time to construct the
hypergraphs $(G_{0},c_{0})$ that are used as inputs to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Theorem
1.1 is a strengthening of Bernáth and Király’s result which says that if
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ is a weak
cover of a symmetric skew-supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$, then there exists a hypergraph
$(H^{*}=(V,E^{*}),w^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+})$ satisfying properties (1) and (2). Our
Theorem 1.1 strengthens their result in two ways. Firstly, our theorem shows
the existence of a hypergraph that not only satisfies properties (1) and (2),
but also satisfies property (3) – i.e., the number of additional hyperedges in
the returned hypergraph is _linear_ in the size of the vertex set. Secondly,
our Theorem 1.1 shows the existence of a strongly polynomial-time algorithm
that returns a hypergraph satisfying the three properties. Although Bernáth
and Király’s result is existential, their proof is algorithmic. However, their
proof is based on induction on $\sum_{e\in E}w(e)$ and consequently, the
straightforward bound on the number of additional hyperedges as well as the
run-time is $O(\sum_{e\in E}w(e))$. Thus, the best run-time bound known for
their algorithm was only pseudo-polynomial. Our main contribution is analyzing
an adaptation of their algorithm to bound the number of additional hyperedges
and the run-time. We mention that property (3) cannot be tightened to
guarantee that $|E^{*}-E|=O(|V|)$ – we were able to construct an example where
$|E^{*}-E|=\Omega(|V|^{2})$ (see Appendix B).

##### Degree-specified skew-supermodular weak cover using (near-uniform)
hyperedges.

Szigeti [64] 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 the degree-specified skew-supermodular weak
cover using hyperedges problem 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$. Bernáth and
Király [5] showed that the same conditions are necessary and sufficient for an
instance $(m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{\geq
0},p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z)$ of the degree-
specified skew-supermodular weak cover using _near-uniform_ hyperedges problem
to be feasible. 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$. As our second result, we show that a feasible instance of the degree-
constrained skew-supermodular weak cover using (near-uniform) hyperedges
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. This immediately implies that both degree-
specified skew-supermodular weak cover using hyperedges problem and degree-
specified skew-supermodular weak cover using near-uniform hyperedges problem
are solvable in strongly polynomial time.

######  Theorem 1.2.

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

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

We emphasize that the run-time above includes the time to construct the
hypergraphs $(G_{0},c_{0})$ that are used as inputs to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. Theorem
1.2 is a strengthening of Szigeti’s result [64] which says that if $m$ and $p$
are two functions satisfying conditions (a) and (b), then there exists a
hypergraph satisfying properties (1)-(3). It is also a strengthening of
Bernáth and Király’s result [5] which says that if $m$ and $p$ are two
functions satisfying conditions (a) and (b), then there exists a hypergraph
satisfying properties (1)-(4). Our Theorem 1.2 strengthens Bernáth and
Király’s result in two ways. Firstly, Theorem 1.2 shows the existence of a
hypergraph that not only satisfies properties (1)-(4), but also satisfies
property (5) – i.e. the number of hyperedges in the hypergraph is _linear_ in
the size of the ground set. Secondly, our Theorem 1.2 shows the existence of a
_strongly polynomial-time_ algorithm that returns a hypergraph satisfying the
five properties. As mentioned previously, although the results of Bernáth and
Király as well as Szigeti are existential, their proof of their result is
algorithmic. However, their proof is based on induction on $K_{p}$ and
consequently, the straightforward bound on the number of hyperedges as well as
the run-time is $O(K_{p})$. Thus, the best run-time known for their algorithm
was only pseudo-polynomial. Our main contribution is analyzing an adaptation
of their algorithm to bound the number of hyperedges and the run-time.

##### Degree-specified simultaneous skew-supermodular weak cover using near-
uniform hyperedges.

Bernáth and Király [5] 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 the degree-constrained _simultaneous_ skew-
supermodular weak cover using _(near-uniform)_ hyperedges problem 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$, where $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ is the function defined by
$p(X)\coloneqq\max\\{q(X),r(X)\\}$ for every $X\subseteq V$ As our fourth
result, we show that a 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)$ of the degree-constrained simultaneous skew-
supermodular weak cover problem 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. This
immediately implies that the degree-specified simultaneous skew-supermodular
weak cover using (near-uniform) hyperedges problem is solvable in strongly
polynomial time.

######  Theorem 1.3.

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

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

We emphasize that the run-time above includes the time to construct the
hypergraphs $(G_{0},c_{0})$ that are used as inputs to
${q}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ and
${r}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$. We note
that conditions (a) and (b) and properties (1)-(4) are identical to that of
Theorem 1.2, but the hypothesis about the function $p$ is different from that
of Theorem 1.2; moreover property (5) also differs between the two theorems.
Theorem 1.3 is a strengthening of a result of Bernáth and Király which says
that if $q$ and $r$ are two skew-supermodular functions, the function $p$ is
defined as the maximum of these two functions, and the functions $m$ and $p$
satisfy conditions (a) and (b), then there exists a hypergraph satisfying
properties (1)-(4). Our Theorem 1.3 strengthens their result in two ways.
Firstly, we show the existence of hypergraphs that not only satisfy properties
(1)-(4), but also satisfies property (5) – i.e. the number of hyperedges in
the hypergraph is _quadratic_ in the size of the ground set. Secondly, we show
the existence of a _strongly polynomial-time_ algorithm that returns a
hypergraph satisfying the five properties. We again note that although Bernáth
and Király’s result is existential, their proof of their result is
algorithmic. However, their proof is based on induction on $K_{p}$ and
consequently, the straightforward bound on the number of hyperedges as well as
the run-time is $O(K_{p})$. Thus, the best run-time known for their algorithm
was only pseudo-polynomial. Our main contribution is analyzing an adaption of
their algorithm to bound the number of hyperedges and the run-time.

We mention that our algorithms for Theorems 1.2 and 1.3 are LP-based. We do
clarify that the underlying LP is solvable in strongly polynomial-time in the
technical sections.

| Degree-specified | Degree-specified
---|---|---
| skew-supermodular | sym. skew-supermodular
| weak cover of | strong cover of
using | one function | two functions | one function | two functions
Edges |  Strong poly [5] |  Strong poly [5] |  NP-comp [19, 50] | NP-comp
|  Pseudo poly [64, 5] |  Pseudo poly [5] |  Pseudo poly [64, 5] |  NP-comp if $K_{q}\neq K_{r}$ [5]
Hyperedges |  Strong poly (Thm 1.2) |  Strong poly (Thm 1.3) |  Strong poly (Coro 7.1) |  Pseudo poly [5]
|  |  |  |  Strong Poly (Coro 7.2)
Near-uniform |  Psuedo poly [5] |  Psuedo poly [5] |  Psuedo poly [5] |  Psuedo poly [5]
Hyperedges |  Strong poly (Thm 1.2) |  Strong poly (Thm 1.3) |  Strong poly (Coro 7.1) |  Strong poly (Coro 7.2)
Table 1: We summarize previous known results and our new results for degree-
specified skew-supermodular cover using hyperedges. We include a row for
covering problems using edges for comparison. In addition to the results in
the above table, we show a strongly polynomial-time algorithm to convert a
weak cover of a symmetric skew-supermodular function to a strong cover of the
same function by merging hyperedges (see Theorem 1.1) which improves on the
pseudo polynomial run-time for the same problem [5]. For all of our results,
we also bound the number of hyperedges in the returned hypergraph.

##### Organization.

We discuss an application of Theorem 1.1 to splitting off in hypergraphs in
Section 1.2. We discuss applications of Theorems 1.2 and 1.3 in Section 7. We
give an outline of the proof techniques for our three theorems (i.e., Theorems
1.1, 1.2, and 1.3) in Section 1.3. We discuss related work in Section 1.4. We
discuss relevant background for our proofs in Section 2. We prove Theorem 1.1
in Section 3. We give a unifying algorithm for weak covering skew-supermodular
functions using hyperedges and prove properties about it in Section 4 which
will subsequently be used in the proofs of Theorems 1.2 and 1.3. We prove
Theorems 1.2 and 1.3 in Sections 5 and 6 respectively. We conclude by stating
two open questions in Section 8. We understand that the paper might be
unusually long compared to most other papers encountered in the literature.
The length is due to the combination of two different results which require
completely different techniques – namely, Theorem 1.1 regarding algorithmic
weak to strong cover by merging and Theorems 1.2 and 1.3 regarding algorithmic
weak cover using near-uniform hyperedges, although the results are unified by
motivations and terminology. For ease of reading, we encourage first-time
readers to go through Sections 1.2, 1.3, 1.4, 7, and 8 in that order before
reading the rest of the technical sections (i.e., Sections 2, 3, 4, 5, and 6).

###  1.2 Application of Algorithmic Weak to Strong Cover by Merging:
Hypergraph Splitting Off

In this section, we show an application of Theorem 1.1 by identifying
connections between the notion of merging hyperedges and a notion of splitting
off in hypergraphs. We refer the reader to Section 7 for applications of
Theorems 1.2 and 1.3.

We now define a notion of splitting off for hypergraphs. To compare and
contrast our definition of splitting off for hypergraphs with the classical
definition of splitting off for graphs, we include both our definition and the
classical definition and distinguish them by identifying them as h-splitting-
off and g-splitting-off (with the convention being that we add the prefix ‘h’
for hypergraph related terminology and the prefix ‘g’ for graph related
terminology). In the definition below, we encourage the reader to consider the
input hypergraph $(G,c)$ to be a graph while considering g-splitting off
terminology and to be a hypergraph while considering h-splitting off
terminology.

######  Definition 1.4.

Let $(G=(V,E),c\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ be a
hypergraph and $s\in V$.

  1. 1.

In _splitting-off almost-disjoint hyperedges operation_ , we pick a pair of
hyperedges $e,f\in\delta_{G}(s)$ such that $e\cap f=\\{s\\}$, pick a positive
integer $\alpha\in\Z_{+}$ such that $\alpha\leq\min\\{c(e),c(f)\\}$, reduce
the weights of hyperedges $e$ and $f$ by $\alpha$, and increase the weight of
a hyperedge $g$ by $\alpha$. Here,

    1. (a)

if we choose $g\coloneqq e\cup f$, then the associated operation will be
called as _h-splitting-off almost-disjoint hyperedges operation_.

    2. (b)

if we choose $g\coloneqq(e\cup f)\setminus\\{s\\}$, then the associated
operation will be called as _g-splitting-off almost-disjoint hyperedges
operation_.

In the above, if $\alpha=c(e)$ (resp. if $\alpha=c(f)$), then we discard the
hyperedge $e$ (resp. hyperedge $f$) from the hypergraph obtained after the
operation; if the hyperedge $g\not\in E$, then we introduce $g$ as a new
hyperedge with weight $c(g)\mathrel{\mathop{\mathchar 58\relax}}=0$ before
performing the weight increase on the hyperedge $g$.

  2. 2.

In the _trimming hyperedge operation_ , we pick a hyperedge
$e\in\delta_{G}(s)$, pick a positive integer $\alpha\in\Z_{+}$, reduce the
weight of the hyperedge $e$ and increase the weight of the hyperedge
$g\coloneqq e\setminus\\{s\\}$. Here,

    1. (a)

if we choose $\alpha\leq c(e)$, reduce the weight of the hyperedge $e$ by
$\alpha$, and increase the weight of the hyperedge $g$ by $\alpha$, then the
associated operation will be called as _h-trimming operation_ (if
$\alpha=c(e)$, then we discard $e$ from the hypergraph obtained after the
operation; if $g\not\in E$, then we add $g$ as a new hyperedge with weight
$c(g)\mathrel{\mathop{\mathchar 58\relax}}=0$ before performing the weight
increase on the hyperedge $g$).

    2. (b)

if we choose $\alpha\leq c(e)/2$, reduce the weight of the hyperedge $e$ by
$2\alpha$, and increase the weight of the hyperedge $g$ by $2\alpha$, then the
associated operation will be called as _g-trimming operation_ (if
$\alpha=c(e)/2$, then we discard $e$ from the hypergraph obtained after the
operation; if $g\not\in E$, then we add $g$ as a new hyperedge with weight
$c(g)\mathrel{\mathop{\mathchar 58\relax}}=0$ before performing the weight
increase on the hyperedge $g$).

  3. 3.

In the _h-splitting-off operation_ , we perform either the h-splitting-off
almost-disjoint hyperedges operation or the h-trimming hyperedge operation.

  4. 4.

In the _g-splitting-off operation_ , we perform either the g-splitting-off
almost-disjoint hyperedges operation or the g-trimming hyperedge operation.

  5. 5.

We will say that a hypergraph
$(G^{*}=(V,E^{*}),c^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+})$ is a

    1. (a)

complete h-splitting-off at $s$ from $(G,c)$ if $(G^{*},c^{*})$ is obtained
from $(G,c)$ by repeatedly applying h-splitting-off operations and
$d_{(G^{*},c^{*})}(s)=0$.

    2. (b)

complete g-splitting-off at $s$ from $(G,c)$ if $(G^{*},c^{*})$ is obtained
from $(G,c)$ by repeatedly applying g-splitting-off operations and
$d_{(G^{*},c^{*})}(s)=0$.

  6. 6.

Let $(G^{*},c^{*})$ be a complete h-splitting-off/g-splitting-off at $s$ from
$(G,c)$. We will say that $(G^{*},c^{*})$ preserves local connectivity if
$\lambda_{(G^{*},c^{*})}(u,v)=\lambda_{(G,c)}(u,v)$ for every distinct $u,v\in
V\setminus\\{s\\}$.

Certain remarks regarding the definitions are in order. Both h-splitting-off
and g-splitting-off _almost-disjoint_ hyperedges operations ensure that the
degree of every vertex $u\in V\setminus\\{s\\}$ is preserved. However, if we
allow the same operations for an arbitrary pair of hyperedges
$e,f\in\delta_{G}(s)$, then degrees of vertices $u\in V\setminus\\{s\\}$ may
not be preserved. Similarly, both h-trimming and g-trimming operations
preserve the degree of every vertex $u\in V\setminus\\{s\\}$. The h-trimming
operation is natural in hypergraphs and has been used in hypergraph literature
before to obtain small-sized certificates for hypergraph connectivity (see
[16]) and for certain notions of directed hypergraph connectivity (see [24]).
We emphasize that both h-splitting-off operation and g-splitting-off
operations preserve the degree of every vertex $u\in V\setminus\\{s\\}$ and
_do not_ increase the coverage/cut values of subsets $X\subseteq
V\setminus\\{s\\}$.

We will primarily be concerned with complete _h-splitting-off_ at a vertex
from a _hypergraph_ and complete _g-splitting-off_ at a vertex from a _graph_.
Complete g-splitting off at a vertex from a _graph_ is equivalent to the
classical and well-studied notion of complete splitting off at a vertex from a
graph (for the definition of the classical notion in graphs, see [24, 52]). To
the best of our knowledge, the definition of complete h-splitting-off at a
vertex from a hypergraph has not appeared in the literature before.

We compare and contrast complete h-splitting-off at a vertex from a hypergraph
and complete g-splitting-off at a vertex from a graph. Complete h-splitting-
off at a vertex $s$ from a hypergraph enables the vertex $s$ to exit the
hypergraph by informing its incident hyperedges about how to merge and trim
themselves in order to preserve connectivity and degrees. In this sense, the
definition of complete h-splitting-off at a vertex from a hypergraph serves
the same role as complete g-splitting-off at a vertex from a graph. On the
other hand, there are important differences between the two notions. Firstly,
complete h-splitting-off at a vertex from a _graph_ may not necessarily be a
graph (owing to the creation of hyperedges of size at least $3$) while
complete g-splitting-off at a vertex from a graph will necessarily be a graph.
Secondly, local connectivity preserving complete g-splitting-off at a vertex
from a graph may not exist777Consider the graph
$(G=(V,E),c\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\\{1\\})$, where
$G$ is the $4$-vertex star graph with the vertex $s$ being the center of the
star. Local connectivity preserving complete g-splitting-off at the vertex $s$
from $(G,c)$ does not exist.. We will see later (in Theorem 1.4) that local
connectivity preserving complete h-splitting-off at a vertex from a hypergraph
will always exist. Thirdly, it is easy to see that local connectivity
preserving complete g-splitting-off at a vertex from a graph is a special case
of degree-specified graph connectivity augmentation using edges
problem888Consider the degree requirement function
$m\mathrel{\mathop{\mathchar 58\relax}}V-\\{s\\}\rightarrow\Z_{\geq 0}$
defined by $m(u)\coloneqq w(\\{u,s\\})$ for every neighbor $u$ of $s$ in $G$
and $m(u)\coloneqq 0$ for every vertex $u$ that is not a neighbor of $s$ in
$G$ and the input graph $(H=(V-\\{s\\},E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ to be $E_{H}\coloneqq
E\setminus\delta_{G}(s)$ and $w_{H}(e)\coloneqq c(e)$ for every $e\in E_{H}$.
(see Section 1 for a definition of this problem). However, local connectivity
preserving complete h-splitting-off at a vertex from a hypergraph is _not_ a
special case of degree-specified hypergraph connectivity augmentation using
hyperedges problem: this is because, degree-specified hypergraph connectivity
augmentation using hyperedges could result in hyperedges that may not be
obtained via a sequence of h-splitting-off operations.

Next, we show that it is always possible to find a local connectivity
preserving complete h-splitting-off at a vertex from a hypergraph in strongly
polynomial time. This theorem can be viewed as a hypergraph counterpart to
Mader’s result showing the existence of a local connectivity preserving
complete g-splitting-off at a vertex from a graph [49, 22, 52, 24].

######  Theorem 1.4.

Given a hypergraph $(G=(V,E),c\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ and a vertex $s\in V$, there exists a strongly
polynomial-time algorithm to find a hypergraph
$(G^{*}=(V,E^{*}),c^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+})$ such that $(G^{*},c^{*})$ is a complete
h-splitting-off at $s$ from $(G,c)$ and $(G^{*},c^{*})$ preserves local
connectivity.

###### Proof.

We begin by proving the existence of a local connectivity preserving complete
h-splitting-off at $s$ from $(G,c)$. We will use Theorem 1.1 with an
appropriate setting of the symmetric skew-supermodular function $p$ and the
hypergraph $(H,w)$. Let $V^{\prime}\coloneqq V\setminus\\{s\\}$. Let the
hypergraph $(H\mathrel{\mathop{\mathchar
58\relax}}=(V^{\prime},E_{H}),w_{H}\mathrel{\mathop{\mathchar
58\relax}}E_{H}\rightarrow\Z_{+})$ be defined by
$E_{H}\coloneqq\\{e-\\{s\\}\mathrel{\mathop{\mathchar
58\relax}}e\in\delta_{G}(s)\\}$ with $w_{H}(e-\\{s\\})\coloneqq c(e)$ for
every $e\in\delta_{G}(s)$. In order to define the function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V^{\prime}}\rightarrow\Z$, we
consider another hypergraph $(J\mathrel{\mathop{\mathchar
58\relax}}=({V^{\prime}},E_{J}),w_{J}\mathrel{\mathop{\mathchar
58\relax}}E_{J}\rightarrow\Z_{+})$ defined by $E_{J}\coloneqq E\setminus
B_{G}(s)$ with $w_{J}(e)\coloneqq c(e)$ for every $e\in E\setminus B_{G}(s)$.
We consider the function $R\mathrel{\mathop{\mathchar
58\relax}}2^{V^{\prime}}\rightarrow\Z_{\geq 0}$ defined by
$R(X)\coloneqq\max\\{\lambda_{(G,c)}(u,v)\mathrel{\mathop{\mathchar
58\relax}}u\in X,v\in V^{\prime}\setminus X\\}$ for every non-empty proper
subset $X\subsetneq V^{\prime}$, $R(\emptyset)\coloneqq 0$, and
$R(V^{\prime})\coloneqq 0$. Now, consider the function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V^{\prime}}\rightarrow\Z$ defined by
$p(X)\coloneqq R(X)-d_{(J,w_{J})}(X)$ for every $X\subseteq{V^{\prime}}$. The
function $p$ is known to be symmetric skew-supermodular (e.g., see Lemma 7.1).
We also note that $b_{(H,w_{H})}(X)\geq p(X)$ for every
$X\subseteq{V^{\prime}}$: for an arbitrary $X\subseteq{V^{\prime}}$, we have
that $b_{(H,w_{H})}(X)+d_{(J,w_{J})}(X)=d_{(G,c)}(X)\geq R(X)$ where the last
inequality is by definition of the function $R$ and hence,
$b_{(H,w_{H})}(X)\geq R(X)-d_{(J,w_{J})}(X)=p(X)$. Applying Theorem 1.1 to the
function $p$ and the hypergraph $(H,w_{H})$, there exists a hypergraph
$(H^{*}=(V^{\prime},E_{H^{*}}),w^{*}\mathrel{\mathop{\mathchar
58\relax}}E_{H^{*}}\rightarrow\Z_{+})$ such that (i) $d_{(H^{*},w^{*})}\geq
p(X)$ for every $X\subseteq V^{\prime}$ and (ii) the hypergraph
$(H^{*},w^{*})$ is obtained by merging hyperedges of the hypergraph
$(H,w_{H})$. Consider the hypergraph $(G^{*}=(V,E^{*}),c^{*})$ obtained from
the hypergraph $(J+H^{*},w_{J}+w^{*})$ by adding the vertex $s$.

We now show that $(G^{*},c^{*})$ is a complete h-splitting-off at $s$ from
$(G,c)$ and $(G^{*},c^{*})$ preserves local connectivity. We note that
property (ii) implies that $(G^{*},c^{*})$ is a complete h-splitting-off at
$s$ from $(G,c)$: this is because, hyperedges of $E_{H^{*}}\setminus E_{H}$
that are obtained by merging hyperedges of $E_{H}$ are equivalent to being
obtained by a sequence of h-splitting-off almost-disjoint hyperedges operation
starting from the hypergraph $(G,c)$ and a final h-trimming operation;
moreover, hyperedges of $E_{H^{*}}\cap E_{H}$ are equivalent to being obtained
by the h-trimming operation from the hypergraph $(G,c)$; finally, we have that
$d_{(G^{*},c^{*})}(s)=0$ by definition. Next, we note that property (i)
implies that $(G^{*},c^{*})$ preserves local connectivity: consider an
arbitrary pair of distinct vertices $u,v\in V^{\prime}$. We recall that
h-splitting-off almost-disjoint hyperedges as well as trimming operations do
not increase the cut value of every subset $X\subseteq V^{\prime}$ and hence,
$\lambda_{(G^{*},c^{*})}(u,v)\leq d_{(G^{*},c^{*})}(X)\leq d_{(G,c)}(X)$ for
every $X\subseteq V^{\prime}$ such that $u\in X,v\in V^{\prime}\setminus X$
and in particular, $\lambda_{(G^{*},c^{*})}(u,v)\leq\lambda_{(G,c)}(u,v)$.
Hence, it suffices to show that $d_{(G^{*},c^{*})}(X)\geq\lambda_{(G,c)}(u,v)$
for every $X\subseteq V^{\prime}$ such that $u\in X,v\in V^{\prime}\setminus
X$. Let $X\subseteq V^{\prime}$ such that $u\in X,v\in V^{\prime}\setminus X$.
We have that

$\displaystyle d_{(G^{*},c^{*})}(X)$
$\displaystyle=d_{(J,w_{J})}(X)+d_{(H^{*},w^{*})}(X)$ (by definition of
$(G^{*},c^{*})$) $\displaystyle\geq d_{(J,w_{J})}(X)+p(X)$ (by property (i) of
$(H^{*},w^{*})$) $\displaystyle=d_{(J,w_{J})}(X)+R(X)-d_{(J,w_{J})}(X)$ (by
definition of the function $p$) $\displaystyle=R(X)$
$\displaystyle\geq\lambda_{(G,c)}(u,v).$ (by definition of the function $R$)

This completes the proof that $(G^{*},c^{*})$ is a complete splitting off at
$s$ from $(G,c)$ and preserves local connectivity.

We now show the existence of a strongly polynomial-time algorithm to obtain
such a hypergraph $(G^{*},c^{*})$. Given $(G,c)$ as input, we can construct
$(H,w_{H})$ and $(J,w_{J})$ as above in strongly polynomial time. There exists
a strongly polynomial-time algorithm to implement
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$, where $p$
is the function defined above (e.g., see Lemma 7.1). By the algorithmic
conclusion of Theorem 1.1, it follows that the hypergraph $(H^{*},w^{*})$
mentioned in the previous paragraph can be obtained in strongly polynomial
time. Finally, we can construct the hypergraph $(G^{*},c^{*})$ using the
hypergraph $(H^{*},w^{*})$ and the hypergraph $(J,w_{J})$ in strongly
polynomial time. ∎

In the proof of Theorem 1.4, we used Theorem 1.1 as a black-box. Instead,
delving into the proof of Theorem 1.1 in the context of the proof of Theorem
1.4 reveals that the following theorem also holds.

######  Theorem 1.5.

Let $(G=(V,E),c\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ be a
hypergraph and $s\in V$. Then, there exists a hypergraph
$(G^{\prime}=(V,E^{\prime}),c^{\prime}\mathrel{\mathop{\mathchar
58\relax}}E^{\prime}\rightarrow\Z_{+})$ obtained from $(G,c)$ by a
h-splitting-off operation such that
$\lambda_{(G^{\prime},c^{\prime})}(u,v)=\lambda_{(G,c)}(u,v)$ for every
distinct $u,v\in V\setminus\\{s\\}$.

We omit the proof of Theorem 1.5 in the interests of brevity. Theorem 1.5
closely resembles the “existential” splitting off results of Mader [49, 22]
and Lovász [48]. Theorem 1.5 does not immediately imply a strongly polynomial-
time algorithm for finding a local connectivity preserving complete splitting
off at a vertex from a given hypergraph. So, Theorem 1.4 may be useful in
algorithmic contexts while Theorem 1.5 may be useful in graph-theoretical
contexts.

###  1.3 Proof Techniques

In this section, we give an outline of our proof techniques for Theorems 1.1,
1.2, and 1.3. We will focus on showing the existential result (instead of the
algorithmic result) for all three theorems. In particular, we will show the
existence of a solution hypergraph in which the number of hyperedges is at
most polynomial in the size of the ground set. Strongly polynomial-time
algorithms follow using known tools in skew-submodular minimization – we refer
the reader to technical sections for details.

####  1.3.1 Weak to Strong cover by Merging

In this section, we describe our proof technique for the existential result in
Theorem 1.1. Let $(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 symmetric
skew-supermodular function such that $(H,w)$ weakly covers the function $p$.
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^{*})$ strongly covers
the function $p$, (2) $(H^{*},w^{*})$ is obtained by merging hyperedges of the
hypergraph $(H,w)$, and (3) $|E^{*}|-|E|=O(|V|)$. We need the following two
operations:

  1. (i)

For hyperedges $e,f\in E$ and an integer $\alpha\leq\min\\{w(e),w(f)\\}$, the
operation Merge $((H,w),e,f,\alpha))$ returns the hypergraph obtained from
$(H,w)$ by decreasing the weight of hyperedges $e$ and $f$ by $\alpha$ and
increasing the weight of the hyperedges $e\cup f$ by $\alpha$.

  2. (ii)

For a hyperedge $e\in E$ and an integer $\alpha\leq w(e)$, the operation
Reduce $((H,w),e,\alpha)$ returns the hypergraph obtained by decreasing the
weight of the hyperedge $e$ by $\alpha$.

We define a set $X\subseteq V$ to be $(p,H,w)$-tight if $b_{(H,w)}(X)=p(X)$.
For a function $p$ and hypergraph $(H,w)$, let $T_{p,H,w}$ denote the family
of $(p,H,w)$-tight sets and let $\mathcal{T}_{p,H,w}$ be the family of
inclusionwise maximal sets in $T_{p,H,w}$.

Our proof of the existential result builds on the techniques of Bernáth and
Király [5] who proved the existence of a hypergraph
$(H^{*}=(V,E^{*}),w^{*}\mathrel{\mathop{\mathchar
58\relax}}E^{*}\rightarrow\Z_{+})$ satisfying properties (1) and (2), so we
briefly recall their techniques. We present the algorithmic version of their
proof since it will be useful for our purposes. The proof in [5] is inductive,
and consequently, the algorithm implicit in their proof is recursive. The
algorithm takes as input a hypergraph $((H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+})$ and a symmetric skew-supermodular function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z)$ such that the
hypergraph $(H,w)$ weakly covers the function $p$. If $w(E)=0$, then the
algorithm is in its base case and returns the empty hypergraph. Otherwise,
$w(E)>0$; the algorithm defines hypergraphs $(H_{0},w_{0})$ and
$(H^{\prime},w^{\prime})$ and the function $p^{\prime}$ by considering two
cases. First, suppose that there exists a hyperedge $e\in E$ that is not
contained in any set of the family $\calT_{p,H,w}$. In this case, the
algorithm defines $(H_{0},w_{0})$ to be the hypergraph on vertex set $V$
consisting of a single hyperedge $e$ with $w_{0}(e)=1$, constructs the
hypergraph $(H^{\prime},w^{\prime})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Reduce}((H,w),e,1)$, and defines the function
$p^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=p-d_{(H_{0},w_{0})}$. Second,
suppose that every hyperedge $e\in E$ is contained in some set of the family
$\mathcal{T}_{p,H,w}$ – it can be shown that there exists a pair of disjoint
hyperedges $e,f\in E$ contained in distinct sets of the family
$\calT_{p,H,w}$. In this case, the algorithm defines $(H_{0},w_{0})$ to be the
empty hypergraph on vertex set $V$, constructs the hypergraph
$(H^{\prime},w^{\prime})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Merge}((H,w),e,f,1)$, and defines the function
$p^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=p$. In both cases, the
algorithm recurses on the inputs $(H^{\prime},w^{\prime})$ and $p^{\prime}$ to
obtain a hypergraph $(H^{*}_{0},w^{*}_{0})$ and returns the hypergraph
$(H^{*},w^{*})=(H^{*}_{0}+H_{0},w^{*}_{0}+w_{0})$. We note that
$w^{\prime}(E^{\prime})=w(E)-1$. Furthermore, it can be shown that the
function $p^{\prime}$ is symmetric skew-supermodular and the hypergraph
$(H^{\prime},w^{\prime})$ weakly covers the function $p^{\prime}$.
Consequently, by induction on $w(E)$, the algorithm can be shown to terminate
in $w(E)$ recursive calls and returns a hypergraph satisfying properties (1)
and (2). Moreover, the number of new hyperedges in the returned hypergraph is
at most the number of recursive calls where the Merge operation is performed,
which is also at most $w(E)$. Thus, in order to reduce the number of new
hyperedges and to design a strongly polynomial-time algorithm, our goal is to
reduce the recursion depth of the algorithm.

We now describe our adaptation of the above-mentioned Bernáth and Király’s
algorithm to reduce the recursion depth. Similar to Bernáth and Király’s
algorithm, our algorithm also takes as input a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$ and a
symmetric skew-supermodular function $p\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ such that the hypergraph $(H,w)$ weakly covers
the function $p$. However, unlike Bernáth and Király’s algorithm, our
algorithm requires the inputs $(H,w)$ and $p$ to satisfy two additional
conditions: (a) every hyperedge $e\in E$ is contained in some set of
$\mathcal{T}_{p,H,w}$ and (b) the degree of every vertex in $(H,w)$ is non-
zero – we show that these conditions are without loss of generality since an
arbitrary instance can be reduced to an instance satisfying these conditions
(see Section 3). Our algorithm is also recursive and its base case is the same
as that of Bernáth and Király’s algorithm (i.e., $w(E)=0$). During recursive
cases (i.e., if $w(E)>0$), instead of performing one of the two (i.e., Merge
or Reduce) operations, our algorithm performs both operations in a sequential
fashion. In particular, we find a pair of disjoint hyperedges $e,f\in E$
contained in distinct sets of $\calT_{p,H,w}$ (such a pair exists by condition
(a) and the arguments of Bernáth and Király mentioned above). Next, instead of
performing one Merge operation (as was done by Bernáth and Király’s
algorithm), we perform as many Merge operations as possible using the
hyperedges $e$ and $f$. Formally, let

$\alpha^{M}\mathrel{\mathop{\mathchar
58\relax}}=\max\left\\{\alpha\in\Z_{+}\mathrel{\mathop{\mathchar
58\relax}}\text{hypergraph returned by }\textsc{Merge}((H,w),e,f,\alpha)\text{
weakly covers }p\right\\}.$

We let $(H^{M},w^{M})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Merge}((H,w),e,f,\alpha^{M})$ and
$p^{M}\mathrel{\mathop{\mathchar 58\relax}}=p$. Next, instead of recursing on
$((H^{M},w^{M}),p^{M})$ (as was done by Bernáth and Király’s algorithm), we
perform as many Reduce operations as possible on the newly created hyperedge
$e\cup f$. Formally, let

$\alpha^{R}\mathrel{\mathop{\mathchar 58\relax}}=\max\left\\{\alpha\in\Z_{\geq
0}\mathrel{\mathop{\mathchar 58\relax}}\text{hypergraph returned by
}\textsc{Reduce}((H^{M},w^{M}),e\cup f,\alpha)\text{ weakly covers
}(p^{M}-d_{(H_{0}^{\alpha},w_{0}^{\alpha})})\right\\},$

where $(H_{0}^{\alpha},w_{0}^{\alpha})$ denotes the hypergraph on vertex set
$V$ consisting of a single hyperedge $e\cup f$ with $w_{0}^{\alpha}(e\cup
f)=\alpha$. We construct the hypergraph
$(H_{0},w_{0})\mathrel{\mathop{\mathchar
58\relax}}=(H_{0}^{\alpha^{R}},w_{0}^{\alpha^{R}})$, the hypergraph
$(H^{R},w^{R})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Reduce}((H^{M},w^{M}),e\cup f,\alpha^{R})$ and define the
function $p^{R}\mathrel{\mathop{\mathchar
58\relax}}=p^{M}-d_{(H_{0}^{\alpha^{R}},w_{0}^{\alpha^{R}})}$. This immediate
reduce step ensures that the hypergraph $(H^{R},w^{R})$ and the function
$p^{R}$ satisfy condition (a) – i.e., every hyperedge in $(H^{R},w^{R})$ is
contained in some set of $\mathcal{T}_{p^{R},H^{R},w^{R}}$. Finally, we
compute sets $\mathcal{Z}\mathrel{\mathop{\mathchar 58\relax}}=\\{u\in
V\mathrel{\mathop{\mathchar 58\relax}}b_{(H^{R},w^{R})}(u)=0\\}$ and
$V^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=V-\mathcal{Z}$, hypergraph
$(H^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=(V^{\prime},E^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=E^{R}),w^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=w^{R})$, and
define the function $p^{\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V^{\prime}}\rightarrow\Z$ by
$p^{\prime}(X)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{p(X\cup
R)\mathrel{\mathop{\mathchar 58\relax}}R\subseteq\mathcal{Z}\\}$ for every
$X\subseteq V^{\prime}$ – this final step can be viewed as a clean up step
since it gets rid of vertices that are not incident to any hyperedges (and
revises the function $p$ appropriately). This clean up step ensures that the
hypergraph $(H^{\prime},w^{\prime})$ satisfies condition (b) – i.e., the
degree of every vertex in $(H^{\prime},w^{\prime})$ is non-zero. It can be
shown that the function $p^{\prime}$ is symmetric skew-supermodular and the
hypergraph $(H^{\prime},w^{\prime})$ weakly covers the function $p^{\prime}$.
Furthermore, the function $p^{\prime}$ and hypergraph
$(H^{\prime},w^{\prime})$ satisfy conditions (a) and (b). We recursively call
the algorithm on input $((H^{\prime},w^{\prime}),p^{\prime})$ to obtain a
hypergraph $(H_{0}^{*},w_{0}^{*})$. We obtain the hypergraph $(G,c)$ from
$(H_{0}^{*},w_{0}^{*})$ by adding the vertices $\mathcal{Z}$ and return the
hypergraph $(G+H_{0},c+w_{0})$. By induction on the total weight of hyperedges
in the input hypergraph, it can be shown that our algorithm returns a
hypergraph satisfying properties (1) and (2) and also terminates in finite
number of recursive calls.

Next, we sketch our proof to show that the recursion depth of our algorithm is
$|E|+O(|V|)$. We note that this also bounds the number of new hyperedges in
the hypergraph returned by the algorithm, and consequently this hypergraph
also satisfies property (3). Let $\ell$ be the number of recursive calls made
by the algorithm on the input instance $((H,w),p)$. We partition the set
$[\ell]$ of recursive calls into two parts: let $P_{1}\subseteq[\ell]$ be the
set of recursive calls during which the merged hyperedge $e\cup f$ survives in
the hypergraph $(H^{\prime},w^{\prime})$ that is input to the subsequent
recursive call and $P_{2}\subseteq[\ell]$ be the recursive calls during which
the merged hyperedge $e\cup f$ does not survive in the hypergraph
$(H^{\prime},w^{\prime})$ that is input to the subsequent recursive call. We
note that $[\ell]=P_{1}\uplus P_{2}$. First, we bound $P_{1}$ by $O(|V|)$ as
follows: for $i\in[\ell]$, consider the maximal tight set family
$\mathcal{T}_{i}=\mathcal{T}_{p_{i},H_{i},w_{i}}$ where
$((H_{i},w_{i}),p_{i})$ is the input to the $i^{th}$ recursive call. Also, let
$\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$ and $V_{i}$ is the ground set of the input to the $i^{th}$
recursive call. We show that $\mathcal{T}_{\leq i}$ is laminar for every
$i\in[\ell]$ (Lemma 3.11). 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. Consequently,
$|\mathcal{T}_{\leq i}|$ is not suitable as a potential function to measure
progress. Instead, we use the potential function
$\phi(i)\mathrel{\mathop{\mathchar 58\relax}}=|\mathcal{T}_{\leq
i}|+3|\mathcal{Z}_{\leq i-1}|$, where $\mathcal{Z}_{\leq i}$ is the union of
the sets $\mathcal{Z}$ computed up to the $i^{th}$ recursive call. We show
that $\phi(i)$ is non-decreasing and strictly increases if $i\in P_{1}$ (3.4
in Lemma 3.12). Consequently, $|P_{1}|=O(|V|)$.

Secondly, we bound $|P_{2}|$ as follows. We use a lookahead-potential
function: let $\Phi_{1}(i)$ be the number of recursive calls between $i$ and
$\ell$ during which the merged hyperedge $e\cup f$ survives in the hypergraph
$(H^{\prime},w^{\prime})$ that is input to the subsequent recursive call and
let $\Phi(i)\mathrel{\mathop{\mathchar 58\relax}}=|E_{i}|+\Phi_{1}(i)$, where
$E_{i}$ is the set of hyperedges in the hypergraph $(H_{i},w_{i})$ input to
the $i^{th}$ recursive call. We show that $\Phi(i)$ is non-increasing and
strictly decreases if $i\in P_{2}$ (3.5 in Lemma 3.12). Hence,
$|P_{2}|\leq\Phi(1)-\Phi(\ell)\leq\Phi(1)\leq|E_{1}|+|P_{1}|=|E|+O(|V))$,
where the last equality is because of the bound on $|P_{1}|$ from the previous
paragraph.

Our key technical contributions are twofold. Our first key technical
contribution is identifying conditions (a) and (b) under which $\calT_{p,H,w}$
becomes a disjoint family. We ensure that conditions (a) and (b) hold in every
recursive call by performing _immediate_ reduction and clean-up steps in the
algorithm. Our second key technical contribution is identifying appropriate
potential functions to measure progress of the algorithm. The disjointness of
$\calT_{p,H,w}$ was helpful in bounding the number of recursive calls
corresponding to $P_{1}$. However, bounding the number of recursive calls
corresponding to $P_{2}$ required a lookahead-potential function that relates
$P_{2}$ to $P_{1}$. As discussed above, the additive $|E|$ in the recursion
depth comes from the bound on $|P_{2}|$.

####  1.3.2 Degree-specified simultaneous skew-supermodular weak cover using
near-uniform hyperedges

In this section, we describe our proof technique for the existential results
in Theorems 1.2 and 1.3. We will consider the setting of Theorem 1.3 since it
is more general than the setting of Theorem 1.2. We will distinguish between
the two settings later after we setup 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.2). 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$, and (5) $|E|=O(|V|)$. Our proof of
the existential result builds on the techniques of Bernáth and Király [5] 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. The proof in [5] 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 hyperedge999The 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 (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 D.4 for the definition of generalized polymatroid) and
consequently, all its extreme points are integral.

With these three properties, their algorithm proceeds as follows. If
$K_{p}=0$, then the algorithm is in its base case and it returns the empty
hypergraph. 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
computes revised functions $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\Z$ as $m^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}=m-\chi_{A}$ and $p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z$ as $p^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}=p-b_{H_{0},w_{0}}$. Then, the algorithm recurses on the inputs
$m^{\prime\prime}$ and $p^{\prime\prime}$ to obtain a hypergraph
$(H_{0}^{*},w_{0}^{*})$ and returns the hypergraph
$(H_{0}^{*}+H_{0},w_{0}^{*}+w_{0})$. It can be shown that $m^{\prime\prime}$
is a non-negative 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 $(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 and to design a strongly polynomial-time algorithm, our goal
is to reduce the recursion depth of the algorithm.

We now describe our adaptation of the above-mentioned Bernáth and Király’s
algorithm to reduce the recursion depth. We make three modifications to their
algorithm. Firstly, we require that the input function $m$ to our algorithm is
_positive_ (i.e. $m\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\Z_{+}$)
as opposed to just being non-negative. We show that this assumption is without
loss of generality since an arbitrary instance can be reduced to such an
instance (see Sections 5 and 6).

Secondly, 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})$ and revising $m$ and $p$
accordingly. We describe this formally now: 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\\},$

where $(H_{0}^{\beta},w_{0}^{\beta})$ is the hypergraph on vertex set $V$
consisting of a single hyperedge $A$ with weight $w_{0}^{\beta}(A)=\beta$. We
construct $(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\\}$ and
$V^{\prime\prime}\mathrel{\mathop{\mathchar 58\relax}}=V-\mathcal{Z}$, 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}\\}$, and 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, the algorithm recurses on the input tuple
$(p^{\prime\prime},m^{\prime\prime})$ to obtain a hypergraph
$(H_{0}^{*},w_{0}^{*})$; it obtains the hypergraph $(G,c)$ by adding vertices
$\mathcal{Z}$ to $(H_{0}^{*},w_{0}^{*})$, and returns $(G+H_{0},c+w_{0})$.

Our third 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)$, but we force hyperedges chosen in the
subsequent recursive call to be correlated with the hyperedges 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^{\prime\prime}$ such that $A^{\prime\prime}$ has the
largest overlap with the hyperedge $A$ chosen in the immediate previous
recursive call subject to $\chi_{A^{\prime\prime}}\in
Q(p^{\prime\prime},m^{\prime\prime})$.

By induction on $K_{p}$ (similar to Bernáth and Király’s proof), it can be
shown that our algorithm returns a hypergraph satisfying (1)–(4) and also
terminates in finite number of recursive calls. Here, we 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 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 4.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 4.9). 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 4.17 and 6.2
in Lemma 6.3). 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.1). 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.4). 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 third
modification in our algorithm – i.e., by correlating the hyperedge chosen in
the subsequent recursive call with the hyperedge chosen in the current
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.4 which in turn relies
on Lemmas 5.2 and 5.3). 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 6.1). 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 6.2). 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$ (6.1 in Lemma 6.3). 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.1.

Our first modification to Bernáth and Király’s algorithm (where we transformed
the input function $m$ to be strictly positive as opposed to just being non-
negative) can be viewed as a clean-up step—if $m(u)=0$ for an element $u\in
V$, then we cannot add any hyperedges containing $u$, so we might as well get
rid of such vertices $u$. This transformation is also helpful while analyzing
the recursion depth. Our computation of the set $\mathcal{Z}$ and definition
of revised functions $p^{\prime\prime}$ and $m^{\prime\prime}$ over the ground
set $V^{\prime\prime}=V-\mathcal{Z}$ helps in ensuring that the input tuple
$(p^{\prime\prime},m^{\prime\prime})$ to the next recursive calls satisfies
the hypotheses (a) and (b) and moreover, $m^{\prime\prime}$ is a strictly
positive function.

######  Remark 1.2.

Our second modification to Bernáth and Király’s algorithm is necessary to
bound the recursion depth to be polynomial in the size of the ground set $V$.
Our proof for covering two functions shows that the algorithm with the first
and second modifications already has recursion depth that is quadratic in the
size of the ground set $V$.

######  Remark 1.3.

As noted in the previous remark, the third modification is not necessary to
bound the recursion depth to be polynomial in the size of the ground set $V$.
We exploit the third modification in the setting of covering one function to
improve the recursion depth from quadratic to linear in the size of the ground
set.

For covering two functions, our main technical contribution is identifying
appropriate potential functions to measure progress of the algorithm. 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 obtaining an improved bound on the
recursion depth for covering one function, we had to modify the algorithm
further – we correlated the choice of the hyperedge in the subsequent
recursive call with the hyperedge chosen in the current recursive call. Our
main technical contribution in the analysis for covering two functions is
proving that such a correlation leads to quantifiable progress within two
recursive calls. This involves technically challenging uncrossing arguments.

###  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
[24, 52, 60, 65, 61, 62]). 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
[42, 16, 63, 3, 17, 41, 40, 45, 38, 57]. 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.

A notion of hypergraph splitting off motivated by hypergraph connectivity
augmentation applications has been studied in the literature before [2, 18,
6]. These works have explored local connectivity preserving complete
g-splitting off at a vertex $s$ from a hypergraph under the assumption that
all hyperedges incident to the vertex $s$ are edges (i.e, have size at most
$2$). In contrast, our result shows that a local connectivity preserving
complete h-splitting off at a vertex $s$ from a hypergraph exists and can be
found in strongly polynomial time irrespective of the size of the hyperedges
incident to the vertex $s$.

Hypergraphs can alternatively be represented as bipartite graphs and
consequently, the notion of local connectivity preserving operations in
hypergraphs can be mapped to the notion of _element connectivity_ preserving
operations in bipartite graphs (see [34, 15] for the definition of element
connectivity). Element connectivity is an intermediate notion between edge
connectivity and vertex connectivity. Vertex connectivity preserving splitting
off in graphs have been studied before [37, 47] but these notions appear to be
different from our definition of complete h-splitting off at a vertex from a
hypergraph.

The rank of a hypergraph is the size of its largest hyperedge. Hypergraph
local connectivity augmentation using _rank- $t$_ hyperedges of minimum total
weight problem is a variant of the hypergraph local connectivity augmentation
using hyperedges problem (see Section 7.2 for the definition of the latter
problem) where the returned hypergraph is additionally required to have rank
at most $t$ (where $t$ is an input integer). Thus, graph local connectivity
augmentation using edges of minimum total weight is a special case of
hypergraph local connectivity augmentation using rank-$2$ hyperedges of
minimum total weight. Although graph local connectivity augmentation using
edges of minimum total weight is polynomial-time solvable [67, 8, 23, 21, 27,
7, 54, 4, 44], hypergraph local connectivity augmentation using rank-$2$
hyperedges of minimum total weight is NP-hard (i.e., hypergraph local
connectivity augmentation using edges of minimum total weight is NP-hard)
[19]. In a surprising twist, independent works by Cosh [18], Nutov [55], and
Bernáth and Király [6] have shown that hypergraph local connectivity
augmentation using hyperedges of minimum total weight problem admits an
optimum 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 the degree-specified symmetric skew-supermodular strong cover using edges
and at most one hyperedge problem. We note that their proof technique does not
generalize to obtain near-uniform hyperedges or to address simultaneous cover
of two functions.

##  2 Preliminaries

We denote the sets of _reals_ , _non-negative reals_ , _positive reals_ ,
_integers_ , _non-negative integers_ , and _positive integers_ by
$\mathbb{R}$, $\mathbb{R}_{\geq 0}$, $\mathbb{R}_{+}$, $\mathbb{Z}$,
$\mathbb{Z}_{\geq 0}$, and $\mathbb{Z}_{+}$ respectively. For a positive
integer $n$, we use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. For a finite
set $V$, we use $2^{V}$ to denote all subsets of $V$. We denote the value of
the _indicator function_ for a statement $S$ by $\mathbbm{1}_{S}$, i.e.
$\mathbbm{1}_{S}=1$ of $S$ is true and $0$ otherwise.

Let $V$ be a finite set. The _characteristic vector_ of a set $X\subseteq V$
is denoted by $\chi_{X}\in\\{0,1\\}^{V}$ where $\chi_{X}(u)=1$ if $u\in X$ and
$0$ otherwise for every $u\in V$. Let $X,Y\subseteq V$. We will denote
$X\setminus Y$ by $X-Y$ and $X\cup Y$ by $X+Y$. If $Y$ consists of a single
element $y$, then $X-\\{y\\}$ and $X+\\{y\\}$ are abbreviated as $X-y$ and
$X+y$, respectively. Let $\calF\subseteq 2^{V}$ be a family of subsets of $V$.
A set $T\subseteq V$ is a _transversal_ for the family $\calF$ if each set in
$\calF$ has non-empty intersection with the set $T$. The family $\calF$ is a
_disjoint family_ if $X\cap Y=\emptyset$ for every $X,Y\in\calF$, a _chain
family_ if either $X\subseteq Y$ or $Y\subseteq X$ for every $X,Y\in\calF$,
and a _laminar family_ if either $X\cap Y=\emptyset$ or $X\subseteq Y$ or
$Y\subseteq X$ for every $X,Y\in\calF$. We recall that the size of a laminar
family $\mathcal{F}\subseteq 2^{V}$ is at most $2|V|$. For a subset
$U\subseteq V$, we define the projection of $\mathcal{F}$ to $U$ as
$\mathcal{F}|_{U}\mathrel{\mathop{\mathchar 58\relax}}=\\{X\cap
U\mathrel{\mathop{\mathchar 58\relax}}X\in\mathcal{F}\\}-\\{\emptyset\\}$ (we
will use the convention that $\mathcal{F}|_{U}$ is a set and not a multi-set).
The next lemma shows that the projection of a laminar family is also laminar
and the size of the projection is comparable to that of the original family.
We give a proof in Section C.1.

######  Lemma 2.1.

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

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\mathbb{R}$ be a
set function over a finite ground set $V$. The function $p$ is _monotone_ if
$p(X)\leq p(Y)$ for every $X\subseteq Y\subseteq V$. If the function $p$ is
locally supermodular for every $X,Y\subseteq V$, then the function $p$ is said
to be _supermodular_. If the reverse of the local-supermodular inequality
holds for every $X,Y\subseteq V$, then the function $p$ is said to be
_submodular_. We recall that for a hypergraph
$(H=(V,E),w\mathrel{\mathop{\mathchar 58\relax}}E\rightarrow\Z_{+})$, the cut
function $d_{(H,w)}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z_{\geq 0}$ is symmetric submodular and the
coverage function $b_{(H,w)}\mathrel{\mathop{\mathchar
58\relax}}2^{V}\rightarrow\Z_{\geq 0}$ is monotone submodular [24]. A set
$X\subseteq V$ is said to be a _$p$ -maximizer_ if
$p(X)=\max\\{p(Z)\mathrel{\mathop{\mathchar 58\relax}}Z\subseteq V\\}$. We use
the notation $Z\coloneqq\arg\max\\{p(Z)\mathrel{\mathop{\mathchar
58\relax}}Z\subseteq V\\}$ to denote an arbitrary set $Z\subseteq V$ such that
$p(Z)\geq p(X)$ for every $X\subseteq V$ (similarly for minimizers of the
function $p$). For a subset $Z\subseteq V$, the _contracted function_
${p}/_{Z}\mathrel{\mathop{\mathchar 58\relax}}2^{V-Z}\rightarrow\Z$ is defined
as ${p}/_{Z}(X)\coloneqq\max\\{p(X\cup R)\mathrel{\mathop{\mathchar
58\relax}}R\subseteq Z\\}$. We note that if $p$ is a skew-supermodular
function and $Z\subseteq V$, then ${p}/_{Z}$ is skew-supermodular. Moreover,
if $p$ is a symmetric function and $Z\subseteq V$, then ${p}/_{Z}$ is
symmetric. For a function $m\mathrel{\mathop{\mathchar
58\relax}}V\rightarrow\R$ and a subset $Z\subseteq V$, we define the
_restricted function_ ${m}\backslash_{Z}\mathrel{\mathop{\mathchar
58\relax}}V-Z\rightarrow\R$ as ${m}\backslash_{Z}(u)\coloneqq m(u)$ for every
$u\in V-Z$.

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

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 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}$ have size
of the order of the size of the hypergraph input to
${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}$. We give a
proof in Section D.1.

######  Lemma 2.2.

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, $S,T\subseteq V$ be disjoint sets, and $y\in\R^{V}$ be a
vector. Then,
${p}\text{-}\mathtt{max}\text{-}\mathtt{wc}\text{-}\mathtt{Oracle}((G,w),S,T,y)$
and ${p}\text{-}\mathtt{max}\text{-}\mathtt{Oracle}(S,T,y)$ can be implemented
to run in $\poly(|V|,|E|)$ time using at most $|V|+1$ queries to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$.

##  3 Weak to Strong Cover in Strongly Polynomial Time

In this section, we show the following main result: See 1.1

Our proof of Theorem 1.1 will require the following definitions.

######  Definition 3.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a set
function and $(H=(V,E),w)$ be a hypergraph. We will say that the hypergraph
$H$ is _non-empty_ if $E\neq\emptyset$. A set $X\subseteq V$ is said to be
_$(p,H,w)$ -tight_ if $b_{(H,w)}(X)=p(X)$. We let $T_{p,H,w}$ denote the
family of $(p,H,w)$-tight sets and $\calT_{p,H,w}$ denote the family of
_inclusion-wise maximal_ sets of $T_{p,H,w}$. For a hyperedge $e\in E$, we let
$\tau_{p,H,w}(e)$ denote an arbitrary set in $T_{p,H,w}$ that contains $e$; if
there is no such set, then we will use the convention that $\tau_{p,H,w}(e)$
is undefined. Additionally, we define two operations as follows:

  1. 1.

For hyperedges $e,f\in E$ and an integer $\alpha\leq\min\\{w(e),w(f)\\}$, the
operation $\textsc{Merge}((H,w),e,f,\alpha)$ returns the hypergraph obtained
from $(H,w)$ by decreasing the weight of hyperedges $e$ and $f$ by $\alpha$
and increasing the weight of the hyperedge $e\cup f$ by $\alpha$ (if
$\alpha=w(e)$, then we discard $e$; if $\alpha=w(f)$, then we discard $f$; if
$e\cup f\not\in E$, then we add the hyperedge $e\cup f$ and set its weight to
be $\alpha$).

  2. 2.

For a hyperedge $e\in E$ and an integer $\alpha\leq w(e)$, the operation
$\textsc{Reduce}((H,w),e,\alpha)$ returns the hypergraph obtained by
decreasing the weight of the hyperedge $e$ by $\alpha$ (if $\alpha=w(e)$, then
we discard $e$).

We first describe how to prove Theorem 1.1 under the assumptions that the
input function $p$ and hypergraph $\left(H=(V,E),w\right)$ satisfy the
following two technical conditions:

  1. (a)

every hyperedge $e\in E$ is contained in some $(p,H,w)$-tight set, and

  2. (b)

$b_{(H,w)}(u)\not=0$ for every $u\in V$, i.e. every vertex is contained in
some hyperedge.

Under these assumptions, we will prove Theorem 1.1 using the algorithm that we
describe in Section 3.1 (see Algorithm 1). In Section 3.2, we show certain
properties of set families that will be used in the description and analysis
of our algorithm. In Section 3.3, we show that our algorithm terminates, and
the hypergraph returned by the algorithm satisfies properties (1) and (2) (see
Lemma 3.8 and Lemma 3.10). In Section 3.4, we show that the hypergraph
returned by the algorithm additionally satisfies property (3) (see Lemma
3.12). In Section 3.5, we show that our algorithm can be implemented to run in
strongly polynomial time given oracle access to
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ (see Lemma
3.14). Algorithm 1, Lemma 3.8, Lemma 3.10, Lemma 3.12, and Lemma 3.14 together
complete the proof of Theorem 1.1 under the assumptions that conditions (a)
and (b) hold.

We now describe how to circumvent assumptions (a) and (b) on the input
function $p$ and hypergraph $(H,w)$. Let $e\in E$ be a hyperedge not contained
in any $(p,H,w)$-tight set. Let
$\alpha_{e}^{R}\coloneqq\min\\{w(e),\beta^{R}(e)\\}$, where

$\beta^{R}(e)\coloneqq\min\\{b_{(H,w)}(X)-p(X)\mathrel{\mathop{\mathchar
58\relax}}e\subseteq X\subseteq V\\}.$

We construct the hypergraph $(H_{0}^{e}\mathrel{\mathop{\mathchar
58\relax}}=(V,E_{0}^{e}\mathrel{\mathop{\mathchar
58\relax}}=\\{e\\}),w_{0}^{e}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\\{\alpha^{R}_{e}\\})$. Now, consider the function
$p^{\prime}\coloneqq p-d_{(H_{0}^{e},w_{0}^{e})}$ and the hypergraph
$(H^{\prime},w^{\prime})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Reduce}((H,w),\alpha^{R}_{e})$; we term this operation as
the reduce operation with respect to the hyperedge $e$. Iteratively performing
this reduce operation with respect to every hyperedge $e\in E$ results in a
function $p_{1}$ and a hypergraph $(H_{1}=(V,E_{1}),w_{1})$ such that
$b_{(H_{1},w_{1})}(X)\geq p_{1}(X)$ for every $X\subseteq V$ and also
satisfies condition (a). Furthermore, suppose that
$\mathcal{Z}\coloneqq\\{u\in V\mathrel{\mathop{\mathchar
58\relax}}b_{H_{1},w_{1}}(u)=0\\}$. Then, the function
$p_{2}\coloneqq{p_{1}}/_{\mathcal{Z}}$ and hypergraph
$(H_{2}=(V-\mathcal{Z},E_{1}),w_{1})$ is an instance with
$b_{(H_{2},w_{1})}(X)\geq p_{2}(X)$ for every $X\subseteq V$ and also
satisfies conditions (a) and (b). Finally, we observe that if $(H^{*},w^{*})$
is a hypergraph that strongly covers the function $p_{2}$, then the hypergraph
$(H^{*}+\sum_{e\in E}H_{0}^{e},w^{*}+w_{0}^{e})$ strongly covers the original
function $p$. Moreover, if $(H^{*},w^{*})$ is obtained by merging hyperedges
of $(H_{2},w_{1})$, then the hypergraph $(H^{*}+\sum_{e\in
E}H_{0}^{e},w^{*}+w_{0}^{e})$ is obtained by merging hyperedges of $(H,w)$.
Thus, our final algorithm is to first obtain the instance $(H_{2},w_{1})$ and
an oracle for
${p_{2}}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ using
${p}\text{-}\mathtt{max}\text{-}\mathtt{sc}\text{-}\mathtt{Oracle}$ such that
the instance $(p_{2},H_{2},w_{1})$ is such that $(H_{2},w_{1})$ weakly covers
$p_{2}$ and satisfies the technical conditions (a) and (b), obtain a
hypergraph $(H^{*},w^{*})$ by the procedure described in the previous
paragraph, and finally return $(H^{*}+\sum_{e\in
E}H_{0}^{e},w^{*}+w_{0}^{e})$.

###  3.1 Weak to Strong Cover Algorithm

Our algorithm is recursive and takes two inputs: (1) a hypergraph
$(H=(V,E),w)$, and (2) a symmetric skew-supermodular function
$p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$. We note that in
contrast to the statement of Theorem 1.1, the inputs $(H,w)$ and $p$ to the
algorithm are required to satisfy the two technical conditions (a) and (b)
specified in the previous section. The algorithm returns a hypergraph
$\left(H^{*}=\left(V,E^{*}\right),w^{*}\right)$.

We now give an informal description of the algorithm (refer to Algorithm 1 for
a formal description). If $E=\emptyset$, then the algorithm returns the empty
hypergraph. Otherwise, the algorithm chooses two hyperedges $e,f\in E$ such
that $\tau_{p,H,w}(e)\neq\tau_{p,H,w}(f)$ ($\tau_{p,H,w}(e)$ is well-defined
for every hyperedge $e\in E$ owing to condition (a); in the next section, we
show that $\tau_{p,H,w}(e)$ is unique for every hyperedge $e\in E$ under
condition (a) and also that if $(H,w)$ is not a strong cover of $p$, then
there exists a pair of hyperedges $e,f\in E$ such that
$\tau_{p,H,w}(e)\neq\tau_{p,H,w}(e)$). Next, the algorithm computes the value

$\beta^{M}\coloneqq\min\left\\{b_{(H,w)}(X)-p(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V\text{ and }e\cap X,f\cap X\not=\emptyset\right\\},$

sets $\alpha^{M}\coloneqq\min\\{\beta^{M},w(e),w(f)\\}$, and defines the
hypergraph $(H^{M},w^{M})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Merge}((H,w),e,f,\alpha^{M})$. Next, the algorithm computes
the value

$\beta^{R}\coloneqq\min\left\\{b_{(H^{M},w^{M})}\left(X\right)-p\left(X\right)\mathrel{\mathop{\mathchar
58\relax}}e\cup f\subseteq X\subseteq V\right\\},$

sets $\alpha^{R}\coloneqq\min\\{\beta^{R},w^{M}(e\cup f)\\}$, and defines the
hypergraph $(H^{R},w^{R})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Reduce}((H^{M},w^{M}),e\cup f,\alpha^{R})$. It computes
hypergraph $(H_{0}=(V,E_{0}\mathrel{\mathop{\mathchar 58\relax}}=\\{e\cup
f\\}),w_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\\{\alpha^{R}\\})$ and defines
$p^{R}\mathrel{\mathop{\mathchar 58\relax}}=p-d_{(H_{0},w_{0})}$. Next, the
algorithm computes the set $\mathcal{Z}\coloneqq\\{u\in
V\mathrel{\mathop{\mathchar 58\relax}}b_{(H^{R},w^{R})}(u)=0\\}$, and
recursively calls itself with the inputs
$(H^{\prime}=(V^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=V-\mathcal{Z},E^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=E^{R}),w^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=w^{R})$ and
$p^{\prime}\coloneqq{p^{R}}/_{\mathcal{Z}}$ to obtain a hypergraph
$\left(H_{0}^{*},w_{0}^{*}\right)$. Finally, the algorithm obtains the
hypergraph $(G,c)$ from $(H_{0}^{*},w_{0}^{*})$ by adding the set
$\mathcal{Z}$ of vertices and returns the hypergraph $(G+H_{0},c+w_{0})$.

Algorithm 1 Weak to Strong Cover

$\mathbf{\textsc{Algorithm}}\left(H=(V,E),w,p\right)\mathrel{\mathop{\mathchar
58\relax}}$

1:if $E=\emptyset$ then Base Case:

2: return $(H,w)$.

3:else:

4: Pick a pair of hyperedges $e,f\in E$ s.t.
$\tau_{p,H,w}(e)\not=\tau_{p,H,w}(f)$

5:
$\alpha^{M}\coloneqq\min\begin{cases}\beta^{M}\coloneqq\min\left\\{b_{(H,w)}(X)-p(X)\mathrel{\mathop{\mathchar
58\relax}}X\subseteq V\text{ and }e\cap X,f\cap X\not=\emptyset\right\\}&\\\
\min\left\\{w(e),w(f)\right\\}&\end{cases}$

6: $(H^{M},w^{M})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Merge}\left(\left(H,w\right),e,f,\alpha^{M}\right)$

7:
$\alpha^{R}\coloneqq\min\begin{cases}\beta^{R}\coloneqq\min\left\\{b_{(H,w^{M})}\left(X\right)-p\left(X\right)\mathrel{\mathop{\mathchar
58\relax}}e\cup f\subseteq X\subseteq V\right\\}&\\\ w^{M}(e\cup
f)&\end{cases}$

8: $(H^{R},w^{R})\coloneqq\textsc{Reduce}\left(\left(H^{M},w^{M}\right),e\cup
f,\alpha^{R}\right)$

9: Construct $\left(H_{0}\mathrel{\mathop{\mathchar
58\relax}}=\left(V,E_{0}\mathrel{\mathop{\mathchar 58\relax}}=\left\\{e\cup
f\right\\}\right),w_{0}\mathrel{\mathop{\mathchar
58\relax}}E_{0}\rightarrow\left\\{\alpha^{R}\right\\}\right)$

10: $p^{R}\coloneqq p-d_{(H_{0},w_{0})}$

11: $\mathcal{Z}\coloneqq\left\\{v\in V\mathrel{\mathop{\mathchar
58\relax}}b_{(H^{R},w^{R})}(v)=0\right\\}$

12: $V^{\prime}\coloneqq V-\mathcal{Z}$

13: $p^{\prime}\coloneqq{p^{R}}/_{\mathcal{Z}}$

14: $(H_{0}^{*},w_{0}^{*})\mathrel{\mathop{\mathchar
58\relax}}=\textsc{Algorithm}\left(H^{\prime}=\left(V^{\prime},E^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=E^{R}\right),w^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=w^{R},p^{\prime}\right)$

15: Obtain $(G,c)$ from $(H_{0}^{*},w_{0}^{*})$ by adding vertices
$\mathcal{Z}$

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

###  3.2 Properties of Tight Sets

In this section, we show properties of the set families $T_{p,H,w}$ and
$\calT_{p,H,w}$ which will be useful to show correctness and convergence of
Algorithm 1 in subsequent sections. In particular, Lemma 3.1 below shows an
important property of the family of tight sets and Corollary 3.1 shows that
for every hyperedge $e\in E$, there exists a unique maximal $(p,H,w)$-tight
set containing $e$ under condition (a). Furthermore, Lemma 3.2 shows that the
family $\calT_{p,H,w}$ is disjoint under condition (b), and consequently,
Corollary 3.2 implies that Algorithm 1 4 is well-defined.

######  Lemma 3.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function and let $\left(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ be a hypergraph such that
$b_{(H,w)}(Z)\geq p(Z)$ for every $Z\subseteq V$. Let $X,Y\in T_{p,H,w}$ be
sets such that $X\cap Y\not=\emptyset$. If there exists a hyperedge $e\in E$
such that (1) $e$ intersects the set $X\cap Y$ and (2) $e$ intersects at most
one of the sets $X-Y$ and $Y-X$, then $X\cup Y,X\cap Y\in T_{p,H,w}$.

###### Proof.

We note that the claim holds if $X\subseteq Y$ or $Y\subseteq X$. Suppose that
$X-Y,Y-X\not=\emptyset$. First, suppose that the function $p$ is locally
negamodular at $X$ and $Y$, i.e. $p(X)+p(Y)\leq p(X-Y)+p(Y-X)$. Then, the
following gives us a contradiction:

$\displaystyle b_{(H,w)}(X)+b_{(H,w)}(Y)$ $\displaystyle=p(X)+p(Y)$
$\displaystyle\leq p(X-Y)+p(Y-X)$ $\displaystyle\leq
b_{(H,w)}(X-Y)+b_{(H,w)}(Y-X)$ $\displaystyle<b_{(H,w)}(X)+b_{(H,w)}(Y).$

Here, the first equality is because $X,Y\in T_{p,H,w}$. The second inequality
is because $b_{(H,w)}(Z)\geq p(Z)$ for every $Z\subseteq V$. The final
inequality is because the hyperedge $e$ intersects at most one of the sets
$X-Y$ and $Y-X$. Thus, the function $p$ is locally supermodular at $X$ and
$Y$, i.e. $p(X)+p(Y)\leq p(X\cap Y)+p(X\cup Y)$. Consequently, we have that

$\displaystyle b_{(H,w)}(X)+b_{(H,w)}(Y)$ $\displaystyle=p(X)+p(Y)$
$\displaystyle\leq p(X\cup Y)+p(X\cap Y)$ $\displaystyle\leq b_{(H,w)}(X\cup
Y)+b_{(H,w)}(X\cap Y)$ $\displaystyle\leq b_{(H,w)}(X)+b_{(H,w)}(Y).$

Here, the first equality is because $X,Y\in T_{p,H,w}$. The second inequality
is because $b_{(H,w)}(Z)\geq p(Z)$ for every $Z\subseteq V$. The final
inequality is because the coverage function $b_{(H,w)}$ is submodular. Thus,
all inequalities in the above sequence are in fact equalities, and
consequently we have that $X\cup Y,X\cap Y\in T_{p,H,w}$. ∎

######  Corollary 3.1.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function and let $\left(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ be a hypergraph such that every hyperedge
$e\in E$ is contained in some $(p,H,w)$-tight set and $b_{(H,w)}(Z)\geq p(Z)$
for every $Z\subseteq V$. Then, for every hyperedge $e\in E$, there is a
unique set from the family $\calT_{p,H,w}$ containing the hyperedge $e$.

###### Proof.

Let $e\in E$ be a hyperedge. We note that there exists a $(p,H,w)$-tight set
containing the hyperedge $e$. Consequently, there exists a set in the family
$\calT_{p,H,w}$ containing the hyperedge $e$. By way of contradiction, suppose
that $X,Y\in\calT_{p,H,w}$ are distinct sets containing the hyperedge $e$. We
note that $X-Y,Y-X\not=\emptyset$ by the maximality of the sets
$X,Y\in\calT_{p,H,w}$. Also, $X\cap Y\neq\emptyset$ since $e$ is contained in
$X\cap Y$. Moreover, $e$ is disjoint from both $X-Y$ and $Y-X$. Hence, by
Lemma 3.1, we have that $X\cup Y\in T_{p,H,w}$, contradicting maximality of
the sets $X,Y\in\calT_{p,H,w}$. ∎

The next lemma shows that for a _skew-supermodular_ function $p$ and
hypergraph $(H,w)$ satisfying conditions (a) and (b), the family
$\calT_{p,H,w}$ is disjoint. The corollary following the lemma says that if
the function $p$ is also _symmetric_ and the hypergraph $H$ is non-empty, then
there exist two hyperedges that are each contained in distinct maximal
$(p,H,w)$-tight sets w.r.t. $p$ and $(H,w)$. We note that this makes Algorithm
1 4 well-defined.

######  Lemma 3.2.

Let $p\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\Z$ be a skew-
supermodular function and let $\left(H=(V,E),w\mathrel{\mathop{\mathchar
58\relax}}E\rightarrow\Z_{+}\right)$ be a hypergraph such that every hyperedge
$e\in E$ is contained in some $(p,H,w)$-tight set, $b_{(H,w)}(u)\not=0$ for
every $u\in V$, and $b_{(H,w)}(X)\geq p(X)$ for every $X\subseteq V$. Then,
the family $\calT_{p,H,w}$ is a disjoint family.

###### Proof.

By way of contradiction, let $X,Y\in\calT_{p,H,w}$ be distinct sets such that
$X\cap Y\not=\emptyset$. By maximality of the sets $X,Y$, we also have that
$X-Y,Y-X\not=\emptyset$. Let $u\in X\cap Y$. Since $b_{(H,w)}(u)>0$, there
exists a hyperedge $e\in E$ such that $u\in e$. We note that if either
$e\cap(X-Y)=\emptyset$ or $e\cap(Y-X)=\emptyset$, then the set $X\cup Y\in