{'fraction_non_alphanumeric': 0.04618177692045841, 'fraction_numerical': 0.005843640077158743, 'mean_word_length': 3.9078379507169707, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Polymatroid Functions

We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based on duality and projections, can be used to rederive some structural results that were previously established using more ad hoc methods. We then show that this technique can be used to obtain a polynomial-time algorithm for a certain type of simple difference constraints. Finally we give lower bound results that show that certain possible extensions of these results are probably not feasible.


Introduction
We consider a class of optimization problems that involve determining the maximum value that a function in a particular class C can attain subject to a collection of difference constraints. So written as a mathematical program, these problems are of the form DC[C]: , and the "variable" is the function (or vector) h : 2 n → ℜ + .
We are primarily interested in two classes C of functions. The first is the class Γ * n of entropic functions. If h is an entropic function then the difference h(Y i ) − h(X i ) is equal to h(Y i | X i ), the conditional entropy of Y i conditioned on the knowledge of X i . Thus DC[Γ * ] is the problem of determining the maximum possible entropy subject to conditional entropy constraints. The second is the class Γ n of polymatroid functions. Other classes of functions that will play a role in our story are the class N n of weighted coverage functions (normal functions in the database literature), and the class M n of modular functions.
Observe that for all collections DC of difference constraints, where here DC[C] should be interpreted to mean the optimal objective value. The first inequality follows because modular functions are weighted coverage functions, the second inequality follows because weighted coverage functions are entropic functions, and last inequality follows because entropic functions are polymatroid functions. It will be convenient to refer to these quantities as the modular bound, the coverage bound, the entropic bound and the polymatroid bound, respectively. It is known that for arbitrary difference constraints that the gaps between these bounds can arbitrarily large [ANS17].

Database Applications and Background
Our main motivation for considering these types of optimization problems arises from applications in databases, for example in bounding the cardinality of a table that is formed by joining smaller tables [Ngo22]. The difference constraints express knowledge about the data that might come from some external understanding of the relation between various attributes, or information that is easily obtained from the data. So for example, consider a simple database for US postal service that contains the following three attributes (among others), attribute 1 is zip code, attribute 2 is city and attribute 3 is state. Assume that it is known that that there are at most 50 states, that no state contains more than 2,598 zip codes, that no city is in more than one state, and no state contains more than 9,197 cities. Then suppose one joins together a collection of tables to get a table T consisting of (zip code, city, state) tuples. Then the number of tuples in T can be upper bounded using the following instance of DC[Γ * n ] problem: In particular, if this optimal objective is E then 2 E is an upper bound to the cardinality of the number of tuples in T (essentially because uniform distributions have maximum entropy) [ANS17]. For certain common types of queries, e.g. disjunctive datalog queries, and joins with functional dependencies and/or cardinality constraints, it is know that this entropic bound is asymptotically tight [ANS17,ANS16]. Unfortunately the space of entropic functions is a complicated. For example, if arbitrary linear constraints are allowed (instead of just difference constraints) the problem is not even computable [Li21,KY22]. Thus the interest in the polymatroid bound in the database community derives from the fact that it represents a clearly computable, and potentially even efficiently computable, upper bound.
To date database researchers have largely considered certain classes of difference constraints that commonly/naturally arise in database applications [Ngo22]. Of particular interest to us here are: Acyclic Difference Instances: An acyclic instance is one where the dependency digraph of the difference constraints is acyclic.
In [Ngo18] it was shown that, for acyclic instances the modular bound is equal to the polymatroid bound. The proof technique was to show that every polymatroid function h that satisfies the difference constraints can be converted in a modular function h ′ that also satisfies the difference constraints and that has the same objective value as h. As the modular bound can be computed by a polynomially sized linear program, this observation yields a polynomial time algorithm to compute the entropic/polymatroid bound for acyclic instances. In [AKNS20] it was shown that, for simple instances the coverage bound is equal to the polymatroid bound. The proof technique was to show that every polymatroid function h satisfying the difference constraints could be converted in a weighted coverage function h ′ satisfying the difference constraints and having the same objective value as h. This observation doesn't immediately yield a polynomial time algorithm as the natural linear programming formulation of the coverage bound has exponentially many variables and exponentially many constraints.
There is a rich history of research in this area in the database theory community, that we can't hope to do justice to here, but a good starting point for reader are the surveys [Ngo22,Ngo18]. Also entropy implication problems are central to the area of information theory, see for example the textbooks [Yeu02,Stu05].

Our Contributions
The Dual-Project-Dual Technique We apply a linear programming based technique, which we will call the dual-project-dual technique, that allows us to rederive the results that DC[M n ] = DC[Γ n ] for acyclic instances and DC[N n ] = DC[Γ n ] for simple instances. We then extend these results in various ways.
Our starting point is a natural linear programming formulation P for the problem of computing DC[Γ n ]: where there is a variable h(X) for each subset X of the universe [n], and X ⊥ Y means X ⊆ Y and Y ⊆ X. We will adopt the convention that all variables in our mathematical programs are constrained to be nonnegative unless explicitly mentioned otherwise. An optimal polymatroid function h ′ would then be where the values on the right hand side come from the linear program P . Note that the linear program P has both exponentially many variables and exponentially many constraints. But critically this linear program only has linearly many constraints where the constant on the right-hand-size of the constraint is nonzero (one for each difference constraint). The first step of our dual-project-dual technique is to take the dual of P to obtain a linear program D. If we associate a dual variables σ X,Y , dual variables µ X,Y and dual variables δ i with the three types of constraints in P (in that order), then the dual linear program D is: where excess(Z) is defined as follows: Figure 1 for an illustration of excess(Z).
So the problem modeled by linear program D can be interpreted as a mincost s-t flow problem on a hypergraph L. The vertices of L are the subsets of [n]. Each variable µ X,Y represents a directed edge with no cost and infinite capacity from Y to X, where X Y . The variable δ i represents the capacity on the directed edge from X i to Y i . The cost to buy this capacity is δ i · c i . The variable σ X,Y represents a hyperedge, and σ X,Y = f means f units of flow leave each of X and Y , and f units of flow enters each of X ∩ Y and X ∪ Y . Flow can not be created at any vertex other than the empty set. The objective is to minimize the cost of the bought capacity subject to the constraint that this capacity can support a unit of flow from the source s = ∅ to the sink t = [n]. For the project step of our dual-project-dual technique, we now consider the region ∆ formed by projecting the feasible region for the linear program D down onto the space corresponding to the δ i variables (and perhaps some other variables in D). Then one can form a (potentially smaller) linear program D ′ equivalent to D by replacing the constraints in D by constraints that define ∆.
The final step of the dual-project-dual technique is to take the dual of D ′ to obtain a linear program P ′ that is equivalent to P , but that is potentially smaller and/or simpler than P .
The Dual-Project-Dual Technique for Simple Instances In Section 3 we consider the application of the dual-project-dual technique to simple instances. For simple instances we show that this dual-project process results in the following linear program D S : We then observe that the dual P S of the linear program D S is the natural linear program for optimizing over weighted coverage functions: Here λ V is the weight of the vertex connected to vertices in V in the standard bipartite representation of a weighted coverage function (without loss of generality one can assume that there is only one such vertex). Thus we rederive the fact that DC[N n ] = DC[Γ * n ] = DC[Γ n ] for simple instances. We then consider the separation problem for D S , where the values of δ i 's are given, and the goal is to determine whether this is D S -feasible. We show that this separation problem is equivalent to n related s-t flow problems on a particular subgraph G of L. The vertices in G are the empty set, the singleton sets, and the sets Y i , i ∈ [k]. The edges in G are all the δ i edges from L, and all the µ X,Y edges from L where X and Y are vertices in G and |X| ≤ 1. We then show that a setting of the δ i variables is feasible in D S if and only if for all t ∈ [n] it is possible to route a unit of flow in G from a source s = ∅ to the sink {t}. Note that each of these flow problems is independent, so while each flow has to respect the edge capacities, the aggregate flows over all sinks can exceed the edge capacities. As an immediate consequence, we can conclude that there is a polynomial-time combinatorial algorithm for the separation problem for D s , and the following linear program D ′ S is equivalent to D S : where excess t (Z) is defined as follows: Here the interpretation of f i,t is the flow from X i to Y i in G for the flow problem where the sink is {t}. As D ′ S is of polynomial size, this yields a polynomialtime algorithm to compute the coverage/entropic/submodular bound for simple instances.
The Dual-Project-Dual Technique for Strongly Connected Components In section 4 we consider applying the dual-project-dual technique for computing the polymatroid bound for general difference constraints. Further we consider the effect of the strongly connected components V 1 , . . . V h of the dependency graph for the difference constraints. In this case we consider the projection from the feasible region for D onto the space spanned by the δ i variables, the µ X,Y variables where Y is a subset of some connected component of the dependency graph, and the σ X,Y variables where X ∪ Y is a subset of some connected component of the dependency graph. Without loss of generality, assume V 1 , . . . , V h is a topological sort of the strongly connected components of the dependency graph. We show that the result of such a projection is the following linear program D SCC : where we define excess as follows: The way to think about the problem modeled by the linear program D SCC is that consists of essentially one hypergraph flow problem, as is modeled by the linear program D, for each connected component. Moreover, the flow problems for the connected components are independent with the exception of sharing the capacities of the projection of the difference constraints into the connected components.
The dual of the linear program D SCC is the following linear program P SCC : The linear program P SCC models computing the optimal objective over what we call semimodular functions. A function is semimodular with respect to a partition . So if the strongly connected components are singletons, then a semimodular function is modular. Thus we can conclude that there is always an optimal solution to DC[Γ n ] that is semimodular with respect to the connected components, and we recover the result that the modular bound, the entropic bound and the polymatroid bound are equal for acyclic instances.
As the size of P SCC is bounded by a polynomial function in n times an exponential function of the maximum number of vertices in any strongly connected component, this yields a fixed parameter tractable algorithm for computing the polymatroid bound when the parameter is the maximum number of vertices in any strongly connected component.
Note that given these results one can view the conversion of an optimal polymatroid function to an optimal modular function for acyclic instances in [Ngo18], and the conversion of an optimal polymatroid function into an optimal weighted coverage function for simple instances in [AKNS20], as being equivalent to the dual process of projecting down to the variables in the objective in the dual space.
Lower Bound Reductions Whether the polymatroid bound for arbitrary difference constraints can be computed in polynomial-time is a fascinating, and seemingly challenging, open question. It is also natural to ask whether we can apply our techniques to other natural classes of difference constraints, but even this is challenging. We have a collection of results that illustrate some of the obstacles to extending our results. We show that computing the coverage bound for general difference constraints is NP-hard. We show how to efficiently reduce the problem of computing the polymatroid bound on general difference constraints to computing the polymatroid bound on difference constraints that are a union of an acyclic instance and a simple instance. And we show how to efficiently reduce the problem of computing the polymatroid bound on general difference constraints to computing the polymatroid bound on difference constraints where for all difference constraints i ∈ [k] it is the case that |X i | ≤ 2 and |Y i | ≤ 3. This shows that computing the polymatroid bound for such instances is as hard as computing the polymatroid bound in general.
Whether the polymatroid bound for arbitrary difference constraints can be computed in polynomial-time is a fascinating, and seemingly challenging, open question. It is also natural to ask whether we can apply our techniques to other natural classes of difference constraints, but even this is challenging. We have a collection of results that illustrate some of the obstacles to extending our results. In section 5 we show that computing the coverage bound for general difference constraints is NP-hard. In section 6 we show how to efficiently reduce the problem of computing the polymatroid bound on general difference constraints to computing the polymatroid bound on difference constraints that are a union of an acyclic instance and a simple instance. And we show how to efficiently reduce the problem of computing the polymatroid bound on general difference constraints to computing the polymatroid bound on difference constraints where for all difference constraints i ∈ [k] it is the case that |X i | ≤ 2 and |Y i | ≤ 3. This shows that computing the polymatroid bound for such instances is as hard as computing the polymatroid bound in general.

Formal Definitions
A function h : 2 n → ℜ + is entropic if there exist discrete 5 random variables z 1 , . . . , z n such that for all X ⊆ [n] it is the case that h(X) is the entropy of the marginal distribution on the variables z j where j ∈ X. A function h : 2 n → ℜ + is a weighted coverage function if there exists a positive integer m, a collection of subsets T 1 , . . . T n of [m], and nonnegative weights w 1 , . . . , w m such that h(X) = ). An algorithm A is a fixed parameter tractable algorithm in the parameter k if the running time of A can be bounded by a polynomial in the input size times some function of k.

The Dual Project Dual Approach for Simple Instances
We show in Lemma 1 that the feasible region of the linear program D S is identical to the feasible region of D ′ S . We then show in Lemma 2 and Lemma 3 that for simple instances the linear program D is equivalent to the linear program D ′ S .
Lemma 1. The feasible region of the linear program D S is identical to the feasible region of D ′ S .
Proof. Assume that for some setting of the δ i variables, that D ′ S is infeasible. Then there exists a t ∈ [n] such that the max flow between s = ∅ and {t} is less than 1. Since the value of the maximum s-t flow is equal the value of the minimum s-t cut, there must be a subset C of vertices in G such that s / ∈ C and t ∈ C, where the aggregate capacities entering C is less than one. Thus by taking V := {i ∈ [n] | {i} ∈ C} we obtain a violated constraint for D S .
Conversely, assume that for some setting of the δ i variables, that D S is infeasible. Then there is a nonempty V such that This cut has value less than one.
Thus again by appealing to the fact that the value of the minimum s-t cut is equal to the maximum s-t flow. we can conclude that this setting of the δ i variables is not feasible for D ′ S .
Lemma 2. For simple instances, if a setting of the δ i variables can be extended to a feasible solution for the linear program D then this same setting of the δ variables is feasible for the linear program D ′ S .
Proof. We prove the contrapositive. Consider a setting of the δ i variables that is not feasible for D ′ S . Then we know that there exists a t ∈ [n] such that there is a cut of value less than one that that separates s = ∅ and {t} in G.
Let V be the union of all singleton sets that are on the same side of this cut as {t}. We know that, i∈[k],Xi∩V =∅,Yi∩V =∅ δ i < 1. Now consider the hypergraph L that is the lattice as defined in Section 1.2. Let V ′ be all nodes in L which contain at least one vertex in V and C be the remaining verticies. Then in the hypergraph L the aggregate flow into vertices in V ′ (i.e. out of C) can be at most i∈[k],Xi∩V =∅,Yi∩V =∅ δ i < 1. This is because no µ X,Y edge can cause flow to enter V ′ from C; and no σ X,Y hyperedge can cause flow to leave C as if X ∈ C and Y ∈ C then X ∪ Y ∈ C, and if either X / ∈ C or Y / ∈ C then σ X,Y does not route any net flow out of C.
Lemma 3. For simple instances, if a setting of the δ i variables is feasible for the linear program D ′ S then this same setting of the δ variables can be extended to a feasible solution for the linear program D.
The rest of the section is devoted to proving Lemma 3. We constructively show how to extend a feasible solution for D ′ S to a feasible solution for D by setting µ X,Y and σ X,Y variables. Let q be an integer such that the setting of every δ i , i ∈ [k], variable is an integer multiple of 1/q, and let ǫ = 1/q. Initially µ Xj ,Yj = δ j for each difference constraint j ∈ [k], and all other µ and σ variables are zero. We now give an iterative process to modify these variable settings. The outer loop of the constructive algorithm to iterates over i ∈ [n]. This loop will maintain the following outer loop invariant on the setting of the variables in D: Note this inductive invariant is initially satisfied, if one interprets [0] to be the empty set, and will represent a feasible solution for D when i = n. To extend the inductive hypothesis from i to i + 1, let P i+1 be the collection of simple flow paths in the graph G that each route an ǫ unit of flow from s = ∅ to t = {i + 1} in D ′ S . Our construction then iterates through the paths in P i+1 , which we call the forward path process, and then iterates through these paths again in what we call the restorative process.
The forward path process processes a path P in P i+1 with edges (A 1 , B 1 ) A, B) is the corresponding edge in P ), processing each edge as follows: The restorative process iterates over the paths in P i+1 [i+1], and then iterates over the edges of each P (A, B) is the corresponding edge in P ) is processed as follows: We will show in Lemma 4 that the outer loop of the forward path process maintains the following forward path loop invariant: it an indicator function that is 1 if path P contains the edge (X h , Y h ) in G. Let us call the right-hand side of this constraint the remaining capacity for difference constraint j. 5. Each variable is an integer multiple of ǫ. Otherwise, note that it must be the case that i > t. Notice that upon termination of the forward path process, the forward path loop invariant implies that outer loop invariant is satisfied for i + 1, with the exception of the third invariant. Lemma 5 shows the the restorative process makes this third invariant true, without affecting the other invariants.
Lemma 5. After the restorative process the outer loop invariant holds for i + 1.

The Dual Project Dual Approach for Strongly Connected Components
For convenience we rewrite D SCC as: where D[U ] are the constraints where we define excess σ,µ as follows: and excess δ as follows: Proof. Assume that a setting of the δ variables is not feasible for D SCC . Then there must exist a j such that D[V j ] is infeasible. By Farkas' lemma, if D[V j ] is not feasible, then there is polymatroid function F j on the lattice of subsets of V j such that We now use F j to define a poly-matroid function F on the full lattice as follows: Note that then Z⊆[n] excess δ (Z, V j )F (Z) < F ([n]). Thus by Farkas' lemma D must be infeasible.
Fix a collection of variables δ, µ SCC and σ SCC variables that are feasible for D SCC . We want to show that δ is feasible for D by setting σ and µ appropriately. The proof is by induction on the number of connected components of the dependency graph. The induction invariant is that after j iterations a flow of one has been routed to the set ∪ j i=1 V i in the lattice. Initially, set all σ and µ variables to 0. Say that a unit flow has reached V * := ∪ j−1 i=1 V i inductively. Consider iteration j. We set the now variables as follows. For The value of the δ i are the same in D and D SCC .
For each i ∈ [k] let m(i) be a real number such that for strongly connected For each difference constraint i ∈ [k] we set some µ variables in D as follows. Let the down pushes of flow in D involving difference constraint i that have been constructed so far be: B ℓ to A ℓ , B ℓ−1 to A ℓ−1 , . . ., B 1 to A 1 such that We then connect these down pushes up by setting µ D X1,A1 = δ i if X 1 = A 1 , and setting each µ D Bi,Ai+1 = δ i if B i = A i+1 and i ∈ [ℓ − 1]. The down pushes and these µ variables together route δ i units of flow from Y i to X i in D.

Hardness of Computing Normal Bounds
This section is devoted to proving the following theorem. Recall that the weighted coverage bounds are obtained over functions that are linear combinations of coverage functions. To prove the theorem we will have to define several collections of difference constraints. Thus, we will directly use (X, Y ) or (X, Y, c) to denote a difference constraint; the former hides c for brevity. For a given collection of difference constraints, G, the LP, D S , can be rewritten into the following equivalent form, D ′ S : where the constraints here are equivalent to those in D S by setting V = [n] \ W . Let ∆(G) denote the convex region over δ defined by the constraints in G. We first show the separation problem is hard.
Theorem 2. Given a difference constraint set G and a vectorδ ∈ R |G| ≥0 , checking ifδ ∈ ∆(G) is NP-complete. Further, this remains the case under the extra condition that λδ ∈ ∆(G) for some λ > 1.
We prove this theorem using a reduction from the Hitting Set problem, which is well-known to be NP-complete. In the Hitting Set problem, the input is a set of n elements E = {e 1 , . . . , e n }, a collection S = {S 1 , . . . , S m } of m subsets of E, and an integer k > 0. The answer is true iff there exists a subset L of k elements such that for every set S i ∈ S is 'hit' by the set L chosen, i.e., Consider an arbitrary instance H to the Hitting Set. To reduce the problem to the membership problem w.r.t. ∆(G), we create an instance for computing weighted coverage bounds that has the elements E ′ = E ∪{e * } and the following set G of differece constraints andδ (here we do not specify c X,Y associated with each difference constraint (X, Y ) as it can be arbitrary and we're concerned with the hardness of the membership test): Let G 1 , G 2 , and G 3 denote the difference constraints defined above in each line respectively, and let G := G 1 ∪ G 2 ∪ G 3 . To establish the reduction we aim to show the following lemma.  Letδ(G ′ ) := (X,Y )∈G ′δX,Y . Note that L min ≤ L(∅) =δ(G 1 ) = m k+1 . Therefore, we can have the following conclusions about W min .
-For all S i ∈ S, S i ⊆ W min since otherwise L min ≥δ({(S i , E ′ )}) = m.
Thus, we have shown that only the difference constraints in G 1 can contribute to L min . As a result, As observed above, for all S i ∈ S, S i ⊆ W min , which means (E \ W min ) ∩ S i = ∅. This immediately implies that E \ W min is a hitting set.
To recap, ifδ ∈ ∆(G), we have 1 k+1 |E \ W min | < 1 and therefore the original instance H admits a hitting set E \ W min of size at most k.
Conversely, if the instance H admits a hitting set E ′ of size k, we can show . This direction is essentially identical and thus is omitted.
⊓ ⊔ The above lemma shows checkingδ ∈ ∆(G) is NP-hard. Further, a violated constraint can be compactly represented by W ; thus the problem is in NP. Finally, if we scale upδ by a factor of λ = k+1, we show λq ∈ ∆(G). We consider two cases.
. This completes the proof of Theorem 2.
Using this theorem, we want to show that we can't solve D ′ S in polynomial time unless P = NP. While there exist relationship among the optimization problem, membership problem and their variants [GLS12], in general hardness of the membership problem doesn't necessarily imply hardness of the optimization problem. However, using the special structure of the convex body in consideration, we can show such an implication in our setting. The following theorem would immediately imply Theorem 1.
Theorem 3. We cannot solve LP normal in polynomial time unless P = NP.
Proof. Consider an instance to the membership problem consisting of G and δ. By Theorem 2, we know checkingδ ∈ ∆(G) is NP-complete, even when λδ ∈ ∆(G) for some λ > 1. For the sake of contradiction, suppose we can solve LP normal in polynomial time for any w ≥ 0 over the constraints defined by the same ∆(G). We will draw a contradiction by showing how to exploit it to check δ ∈ ∆(G) in polynomial time. Define It is straightforward to see that R is convex.
Thanks to the claim, we can draw a contradiction if we can test if R = ∅ in polynomial time. However, R is defined on an open set which is difficult to handle. Technically, R is defined by infinitely many constraints but it is easy to see that we only need to consider constraints for δ that are vertices of ∆(G). Further, ∆(G) is defined by a finite number of (more exactly at most 2 n ) constraints (one for each W ). This implies that the following LP, has a strictly positive optimum value iff R = ∅. We solve this using the ellipsoid method. Here, the separation oracle is, given w ≥ 0 and ǫ, to determine if w · (δ −δ) ≥ ǫ for all δ ∈ ∆(G); otherwise it should find a δ ∈ ∆(G) such that w · (δ −δ) < ǫ. In other words, we want to know min δ∈∆(G) w · (δ −δ). If the value is no smaller than ǫ, all constraints are satisfied, otherwise, we can find a violated constraint, which is given by the δ minimizing the value. But, because the oracle assumes w ·δ is fixed, so this optimization is essentially the same as solving LP normal , which can be solved by the hypothetical polynomial time algorithm we assumed to have for the sake of contradiction. Thus, we have shown that we can decide in poly time if R is empty or not.

Hard Special Cases
In this section we present two classes of seemingly simple instances which turn out to be as hard as general instances.

Reduction from General DCs to Acyclic DCs and Simple FDs
Theorem 4. For the problem of computing the polymatroid bound, an arbitrary instance can be converted into another instance in polynomial time without changing the bound, where the difference constraints (DCs) can be divided into two subsets of acyclic DCs and simple functional dependencies (FDs)-further, each FD contains exactly two elements.
Reduction: Suppose we are given an arbitrary instance I consisting of the universe U := [n] and a set G of DCs. The new instance I ′ has U ′ := ∪ i∈[n] {x i , y i } as universe where x i and y i are distinct copies of i and the following set G ′ of DCs. For each i ∈ [n], we first add the following simple functional dependencies to G ′ : Then for each (A, B, d) ∈ G, we create a new DC (A ′ , B ′ , d) by replacing each i ∈ A with x i and each j ∈ B with y j , and add it to G ′ . By construction these DCs are from {x 1 , x 2 , · · · , x n } to {y 1 , y 2 , · · · , y n } and therefore are acyclic.
The following simple observation states that x i and y i are indistinguishable in computing the polymatroid bound for I ′ .
Lemma 8. Let g be a submodular function that satisfies G ′ of I ′ . For any i ∈ [n] and any B ⊆ U ′ such that Proof. By submodularity and a FD in G ′ involving x i , y i , we have: Henceforth, we will show the following to complete the proof of Theorem 4: 1. Given a monotone submodular function f achieving the optimum polymatroid bound for I, we create a monotone submodular function g for I ′ such that f (U ) = g(U ′ ). 2. Conversely, given a monotone submodular function g achieving the optimum polymatroid bound for I ′ , we crate a monotone submodular function f for I such that f (U ) = g(U ′ ).
We first show the first direction. Let h : 2 U ′ → 2 U be a set function that converts a subset of U ′ to a subset of U by counting x i and y i only once for each i ∈ [n]. Formally, i ∈ h(B) iff x i ∈ B or y i ∈ B. Then, we set g(B) := f (h(B)).

Lemma 9. For any
Proof. The first claim follows because if x i or y i is in any of A and B, it is also . Therefore, we only need to show g is monotone and submodular. Showing monotonicity is trivial and is left as an easy exercise. We can show that g is submodular as follows. For any A, B ⊆ U ′ , we have, where the first inequality follows from f 's submodularity and the second from f 's monotonicity and Lemma 9. Thus we have shown the first direction.
This completes the proof of Theorem 4.
6.2 Reduction from General DCs to DCs (X, Y, d) with |X| ≤ 2 Theorem 5. There is a polynomial-time reduction from a general instance to an instance preserving the polymatroid bound, where for each difference constraint (X, Y, d) we have |Y | ≤ 3 and |X| ≤ 2. Further, the new instance satisfies the following: -If |Y | = 3, then |X| = 2 and d = 0.

Reduction:
The high-level idea is to repeatedly replace two variables with a new variable in a difference constraint. We first discuss how to choose two variables to combine. Assume there is a difference constraint (X, Y, d) where |X| > 2. Then we combine an arbitrary pair of elements in X. If |X| ≤ 2 for all difference constraints, and there is a difference constraint where |Y | > 3, we combine arbitrary two variables in Y \X. If there is a difference constraint (X, Y, d) where |X| = 2, |Y | = 3 and d > 0, we combine the two variables in X. It is important to note that we make this replacement in only one difference constraint in each iteration. By renaming, we can assume wlog that we combine variables n − 1 and n into a new variable 0 in a difference constraint (X, Y, d) ∈ G. Then, we create (X ′ , Y ′ , d) and add it to G ′ where What do we have after repeatedly applying this reduction? Let's first see why the reduction process terminates. For a difference constraint (X, Y, d), Define c(X, Y, d) = |X| + |Y | for a non-trivial constraint (X, Y, d). The potential is defined as the total sum of c(X, Y, d) over all non-trivial constraints. Observe that in each iteration, either c(X, Y, d) > c(X ′ , Y ′ , d), or |X ′ | = 1 and |Y ′ | = 2. In the latter case, the resulting non-trivial constraint (X ′ , Y ′ , d) doesn't change in the subsequent iterations. In the former case the potential decreases. Further, initially the potential is at most 2n|G| and the number of non-trivial constraints never increases, where G is the set of difference constraints initially given. Therefore, the reduction terminates in a polynomial number of iterations. It is now straightforward to see that we only have difference constraints of the forms that are stated in Theorem 5 at the end of the reduction.
Reduction Preserves the Polymatroid Bound. We consider one iteration where a non-trivial constraint (X, Y, d) is replaced according to the reduction described above. Let opt and opt ′ be the polymatroid bounds before and after performing the iteration respectively. Let G and G ′ be the sets of the difference constraints before and after the iteration respectively. We first show opt ≥ opt ′ . Let g : {0}∪[n] → [0, ∞) be a monotone submodular function that achieves opt ′ subject to G ′ . Define f : It is immediate that f is montone and submodular from g being monotone and submodular, as we only restricted the function to [n]. The following claim shows that having 0 is equivalent to having n − 1 and n in evaluating g.

⊓ ⊔
We now check if f satisfies G. Because we only replaced (X, Y, d) ∈ G, we only need to show that f satisfies it. We need to consider two case: Finally, f ([n]) = g([n]) = g([n] ∪ {0}) = opt ′ due to Claim 6.2. Since we have shown f is a feasible solution for G, we have opt ≥ f ([n]). Thus, we have opt ≥ opt ′ as desired.
We now show opt ≤ opt ′ . Given f that achieves opt subject to G, we construct g : {0} ∪ [n] → [0, ∞) as follows: We first verify that g is monotone. Consider A ⊆ B ⊆ {0} ∪ [n]. If 0 ∈ A and 0 ∈ B, or 0 ∈ A and 0 ∈ B, it is easy to see that is the case. So, assume 0 ∈ A but 0 ∈ B. -When 0 ∈ A and 0 ∈ B. This case is trivial as g will have the same value as f for all subsets we're considering. [Due to f 's monotonicity] Thirdly, we show that g satisfies G ′ . Suppose we replaced a non-trivial constraint (X, Y, d) with (X ′ , Y ′ , d). We show g(Y ′ ) − g(X ′ ) ≤ d by showing f (Y ) = g(Y ′ ) and f (X) = g(X ′ ). Both cases are symmetric, so we only show f (X ′ ) = g(X). If 0 ∈ X ′ , then clearly we have g(X ′ ) = f (X) since X ′ = X. If 0 ∈ X ′ , then it must be the case that X ′ = X \{n−1, n}∪{0}. By definition of g, we have g(X ′ ) = f (X ′ \ {0} ∪ {n − 1, n}) = f (X) since X ′ \ {0} ∪ {n − 1, n} = X. Now we also need to check g satisfies the consistency constraints we created. So we show -g({0, n − 1, n}) ≤ g({n − 1, n}). Both sides are equal to f ({n − 1, n}) by definition of g.
This completes the proof of Theorem 5.