Definitions for Linear programs for entanglement and key distribution in the quantum internet

QAlgorithms.Papers.Independent.Intakethird100.P35.ConcurrentFeasible

For any natural numbers $n,r$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, any capacity function $c:E\to\mathbb R$, any functions $s,t:\{0,\ldots,r-1\}\to\{0,\ldots,n-1\}$, and any family of real functions $f_i:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$, write $f_{i,e}^0=f_i(e,\mathrm{false})$ and $f_{i,e}^1=f_i(e,\mathrm{true})$. This predicate requires

$$\begin{gathered} f_{i,e}^0\ge0,\quad f_{i,e}^1\ge0\qquad(i<r,\ e\in E),\\ \sum_{i=0}^{r-1}(f_{i,e}^0+f_{i,e}^1)\le c(e)\qquad(e\in E),\\ \sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}(f_{i,e}^0-f_{i,e}^1) +\mathbf 1_{\{r(e)=v\}}(f_{i,e}^1-f_{i,e}^0) \right)=0 \quad(i<r,\ v\ne s(i),\ v\ne t(i)). \end{gathered}$$

There are no distinctness requirements on terminals within or between pairs, and no sign requirements on terminal net outflows. Any negative edge capacity makes feasibility impossible. When $r=0$, the predicate reduces to $0\le c(e)$ for every edge. Empty edge sets are allowed; when $n=0$, the terminal functions can exist only if $r=0$, and the graph also forces $E$ to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P35.ConnectivityFeasible

For a natural number $n$, a type $E$ equipped with a finite enumeration, a graph $G$ with distinct endpoints $\ell(e),\rho(e)\in V=\{0,\ldots,n-1\}$ for each edge, any real capacity function $c:E\to\mathbb R$, a finite terminal set $S\subseteq V$, a real number $z$, and a family of real-valued functions $f^{u,v}:E\times\{0,1\}\to\mathbb R$ indexed by $u,v\in S$ with $u<v$, feasibility means that every such pair satisfies all of the following: $f^{u,v}(e,b)\ge0$ for every edge and both direction indices; $f^{u,v}(e,0)+f^{u,v}(e,1)\le c(e)$ for every edge; $\Delta_{f^{u,v}}(w)=0$ at every vertex $w$ different from both $u$ and $v$; and $z\le\Delta_{f^{u,v}}(u)$, where $\Delta_h(w)=\sum_{e\in E}\bigl(\mathbf1_{\ell(e)=w}(h(e,0)-h(e,1))+\mathbf1_{\rho(e)=w}(h(e,1)-h(e,0))\bigr)$. Each pair has its own full capacity bound; capacities are not summed across pairs. There is no assumption that $c$ or $z$ is nonnegative. If $S$ has fewer than two elements, the condition is vacuous for every real $z$. If there is at least one terminal pair and some edge has negative capacity, the required nonnegative flow values cannot satisfy that edge’s capacity bound.

QAlgorithms.Papers.Independent.Intakethird100.P35.EdgeGraph

For any natural number $n$, including $0$, and any type $E$, an element of this structure consists of two functions $\ell,r:E\to\{0,\ldots,n-1\}$, together with the requirement that $\ell(e)\ne r(e)$ for every $e\in E$. Thus each edge label has two distinct, ordered endpoints. The type $E$ need not be finite, and distinct edge labels may have the same endpoints. If $n=0$, such a structure can exist only when $E$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P35.FiniteLP

For any type $X$, a $\mathrm{FiniteLP}(X)$ consists of a finite ordered list of rows, each row containing a coefficient function $X\to\mathbb R$, a real right-hand side, and a Boolean equality flag, together with an objective coefficient function $o:X\to\mathbb R$. The row list may be empty or contain repeated rows; $X$ itself need not be finite or nonempty. This structure supplies no definition of feasibility, optimization direction, or attained optimum.

QAlgorithms.Papers.Independent.Intakethird100.P35.Flow

For any type $E$, a flow is simply a function $f:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$, assigning two real numbers to each edge label. There are no nonnegativity, capacity, or conservation conditions in this definition. If $E$ is empty, there is exactly one such function.

QAlgorithms.Papers.Independent.Intakethird100.P35.IsSimple

For any natural number $n$, any type $E$, and any graph $G$ specified by endpoint functions $\ell,r:E\to\{0,\ldots,n-1\}$ satisfying $\ell(e)\ne r(e)$, this predicate means that for all $e,f\in E$,

$$\bigl((\ell(e)=\ell(f)\land r(e)=r(f))\lor (\ell(e)=r(f)\land r(e)=\ell(f))\bigr)\implies e=f.$$

In other words, two edge labels with the same endpoints, in either order, must be equal. No finiteness assumption is imposed on $E$; when $E$ is empty, the condition holds vacuously.

QAlgorithms.Papers.Independent.Intakethird100.P35.LPRow

For any type $X$, an $\mathrm{LPRow}(X)$ consists of a function $a:X\to\mathbb R$ called its coefficient function, a real number $b$ called its right-hand side, and a Boolean value $\varepsilon$ called its equality flag. The type $X$ need not be finite or nonempty, and no restrictions on the coefficients or right-hand side, or interpretation of the Boolean flag as a constraint, are included in this structure.

QAlgorithms.Papers.Independent.Intakethird100.P35.LPVariable

For arbitrary types $I,E,D$, this abbreviation denotes the disjoint union

$$\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\},$$

where $0,1$ represent the Boolean values false and true. Thus its elements have exactly three distinct tagged forms: a triple $(i,a,b)$, an element $d\in D$, or the single additional element $\ast$; the tags keep these forms distinct even if the underlying types overlap. No finiteness or nonemptiness assumptions are imposed on $I,E,D$, and the additional element $\ast$ is always present.

QAlgorithms.Papers.Independent.Intakethird100.P35.Packing

For natural numbers $n,r$, an arbitrary edge type $E$, a graph $G$ assigning each edge $e$ distinct endpoints $\ell(e),\rho(e)\in V=\{0,\ldots,n-1\}$, a function $L:E\to\mathbb N$, and terminal maps $s,t:\{0,\ldots,r-1\}\to V$, a packing consists of a natural number $q_i$ for each terminal index $i$ and a path for each indexed occurrence $(i,j)$ with $0\le j<q_i$. The available edges are the labeled copies $(e,a)$ with $e\in E$ and $0\le a<L(e)$; every copy has endpoints $\ell(e),\rho(e)$. Each selected path has a length $d$ with $0\le d<n$, an injective vertex sequence $v_0,\ldots,v_d$ with $v_0=s_i$ and $v_d=t_i$, and a sequence of $d$ copied edges, each joining its consecutive vertices in either orientation. For any two distinct indexed occurrences, every copied edge used by one path must differ from every copied edge used by the other, including when both paths belong to the same terminal index. Vertices may be shared between paths, and different copies of the same original edge are distinct edges. Counts may all be zero. A path of length zero is permitted exactly when its terminals coincide; such paths use no edges, so the disjointness requirement does not restrict how many are selected. If $r=0$, there are no counts or selected paths; if $n=0$, the terminal maps can exist only when $r=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.SimpleEdgePath

For any natural number $n$, any type $E$, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, and any vertices $s,t$, this type consists of the following data: a natural number $l<n$, a vertex sequence $v_0,\ldots,v_l$, and an edge-label sequence $e_0,\ldots,e_{l-1}$, such that all $v_j$ are pairwise distinct, $v_0=s$, $v_l=t$, and, for each $0\le j<l$,

$$(\ell(e_j)=v_j\land r(e_j)=v_{j+1}) \lor (r(e_j)=v_j\land \ell(e_j)=v_{j+1}).$$

Thus traversal may use either order of an edge’s endpoints, and the chosen edge labels are part of the data. No finiteness assumption is made on $E$. Length $0$ is allowed: it gives the single-vertex path exactly when $s=t$; injectivity excludes all positive-length paths when $s=t$. Supplying $s,t$ requires $n>0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.SingleFeasible

For any natural number $n$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$ for every $e\in E$, any real capacity function $c:E\to\mathbb R$, any vertices $s,t$, and any function $f:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$, write $f_e^0=f(e,\mathrm{false})$ and $f_e^1=f(e,\mathrm{true})$. This predicate requires all three conditions:

$$\begin{gathered} f_e^0\ge0,\quad f_e^1\ge0\qquad(e\in E),\\ f_e^0+f_e^1\le c(e)\qquad(e\in E),\\ \sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}(f_e^0-f_e^1) +\mathbf 1_{\{r(e)=v\}}(f_e^1-f_e^0) \right)=0\qquad(v\ne s,\ v\ne t). \end{gathered}$$

The vertices $s,t$ are not required to be distinct, and no sign condition is imposed on their net outflows. A negative capacity on any edge makes the predicate impossible to satisfy. Empty edge sets are allowed, with every displayed sum equal to $0$; supplying $s,t$ requires $n>0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.SteinerCut

For any natural number $n$ and finite subsets $S,A\subseteq\{0,\ldots,n-1\}$, the stated property means that there exist $s,t\in S$ such that $s\in A$ and $t\notin A$. Equivalently, $A$ contains at least one terminal and excludes at least one terminal. The two witnesses are necessarily distinct, but no order between them is required, and no restriction is placed on the membership of vertices outside $S$. The property is false when $S$ has fewer than two elements, when $A$ is empty, or when $A$ is the whole vertex set; in particular, it is always false when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.TerminalPair

For any natural number $n$ and finite subset $S$ of $V=\{0,\ldots,n-1\}$, this is the type of ordered pairs $(u,v)$ such that $u\in S$, $v\in S$, and $u<v$ in the usual order on vertex indices. Thus each pair consists of two distinct terminals, recorded with the smaller one first. The type is empty when $S$ has fewer than two elements, including when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.coefficientRow

For any type $X$, any function $l:(X\to\mathbb R)\to\mathbb R$, any real number $b$, and any Boolean $\varepsilon$, this definition produces a row with right-hand side $b$, equality flag $\varepsilon$, and coefficient at $j\in X$ equal to $l(\delta_j)$, where $\delta_j:X\to\mathbb R$ is $1$ at $j$ and $0$ at every other element. No finiteness or nonemptiness assumption is made on $X$, and no linearity assumption is made on $l$: the definition only evaluates $l$ on these individual coordinate functions.

QAlgorithms.Papers.Independent.Intakethird100.P35.connectivityValue

For a natural number $n$, a type $E$ equipped with a finite enumeration, a graph $G$ assigning each edge distinct endpoints $\ell(e),\rho(e)\in V=\{0,\ldots,n-1\}$, any function $c:E\to\mathbb R$, and a finite terminal set $S\subseteq V$, the defined real number is $\sup\{z\in\mathbb R:\text{there exists a family }(f^{u,v})_{u,v\in S,\ u<v}\text{ satisfying the following conditions}\}$. Each $f^{u,v}$ assigns a nonnegative real number to every edge and each of two direction indices, satisfies $f^{u,v}(e,0)+f^{u,v}(e,1)\le c(e)$ separately for every edge, has $\Delta_{f^{u,v}}(w)=0$ whenever $w\ne u,v$, and has $\Delta_{f^{u,v}}(u)\ge z$, where $\Delta_h(w)=\sum_{e\in E}\bigl(\mathbf1_{\ell(e)=w}(h(e,0)-h(e,1))+\mathbf1_{\rho(e)=w}(h(e,1)-h(e,0))\bigr)$. Different terminal pairs do not share their capacity bounds. This uses the total real supremum operation, which returns $0$ for an empty set or a set unbounded above. In particular, when $|S|<2$, every real $z$ qualifies vacuously and the defined value is $0$; when $|S|\ge2$ and some capacity is negative, no $z$ qualifies and the value is also $0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.copyGraph

For any natural number $n$, any type $E$, any graph $G$ with endpoint functions $\ell,r:E\to\{0,\ldots,n-1\}$ satisfying $\ell(e)\ne r(e)$, and any function $L:E\to\mathbb N$, the defined graph has the same vertex set and edge-label type

$$\{(e,j):e\in E,\ 0\le j<L(e)\}.$$

The left and right endpoints of $(e,j)$ are respectively $\ell(e)$ and $r(e)$, and their inequality is inherited from $G$. An edge with $L(e)=0$ contributes no labels, while an edge with positive $L(e)$ contributes that many distinct labels sharing its endpoints. Neither $E$ nor the resulting edge type is required to be finite. If $n=0$, the supplied graph forces $E$, and hence the resulting edge type, to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P35.cutCapacity

For a natural number $n$, a type $E$ equipped with a finite enumeration, a graph $G$ assigning each edge distinct endpoints $\ell(e),\rho(e)\in V=\{0,\ldots,n-1\}$, any real-valued function $c:E\to\mathbb R$, and a finite subset $A\subseteq V$, the cut capacity is $\sum_{e\in E}c(e)\mathbf1_{\lvert\{\ell(e),\rho(e)\}\cap A\rvert=1}$: each edge contributes its capacity exactly when one endpoint belongs to $A$ and the other does not, and otherwise contributes zero. The edge’s orientation does not affect this condition, and distinct parallel edge labels are counted separately. Capacities need not be nonnegative, so the sum can be negative. It is $0$ when $E$ is empty, when $A$ is empty, or when $A=V$. If $n=0$, the existence of the endpoint maps forces $E$ to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P35.descriptionSize

For any finite type $X$, equipped with a finite enumeration, and any finite linear-program description $P$ consisting of a list of rows and an objective function $X\to\mathbb R$, define its description size to be

$$|X|(m+1)+m,$$

where $m$ is the length of its row list. Each row consists of a coefficient function $X\to\mathbb R$, a real right-hand side, and a Boolean equality flag. The formula counts every listed row, including repeated or zero rows, and applies also when $X$ or the row list is empty; it does not depend on the values of the coefficients, right-hand sides, equality flags, or objective.

QAlgorithms.Papers.Independent.Intakethird100.P35.indexedRows

For any types $I,X$, with a specified finite enumeration of $I$, and any function $f$ assigning to each $i\in I$ a row consisting of coefficients $X\to\mathbb R$, a real right-hand side, and a Boolean equality flag, this definition returns the list obtained by listing every element of $I$ once and applying $f$ in that enumeration order. Its length is $|I|$; it is empty when $I$ is empty, and equal rows can appear repeatedly when distinct indices have the same image. No finiteness assumption is made on $X$.

QAlgorithms.Papers.Independent.Intakethird100.P35.lpCapacity

For arbitrary types $I,E,D$, with a specified finite enumeration of $D$, a function $a:D\to E$, real values $C_d$, a real assignment $x$ on $\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\}$, and an element $e\in E$, this definition returns

$$\sum_{d\in D} \begin{cases} C_d\,x(d),&a(d)=e,\\ 0,&a(d)\ne e, \end{cases}$$

where $x(d)$ is the tagged $D$-coordinate. Neither $C_d$ nor $x(d)$ is required to be nonnegative, $a$ need not be injective or surjective, and $I,E$ need not be finite. The value is zero if $D$ is empty or no $d$ maps to $e$.

QAlgorithms.Papers.Independent.Intakethird100.P35.lpFlow

For arbitrary types $I,E,D$, a real assignment $x$ on the tagged disjoint union $\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\}$, and an element $i\in I$, this definition returns the function $f_i:E\times\{0,1\}\to\mathbb R$ given by $f_i(a,b)=x(i,a,b)$, using the tagged triple coordinate of $x$. There are no sign, capacity, or conservation requirements on this function and no finiteness assumptions on the types; when $E$ is empty, the returned function has empty domain.

QAlgorithms.Papers.Independent.Intakethird100.P35.lpFrequency

For arbitrary types $I,E,D$, a real assignment $x$ on $\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\}$, and an element $d\in D$, this definition returns $x(d)$ at the tagged $D$-coordinate. It imposes no nonnegativity, upper bound, or normalization requirement, and the types need not be finite.

QAlgorithms.Papers.Independent.Intakethird100.P35.lpSlack

For arbitrary types $I,E,D$ and a real assignment $x$ on $\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\}$, this definition returns the coordinate $x(\ast)$ at the single additional element. This is an unrestricted real number; no finiteness or nonemptiness assumptions on $I,E,D$ are required.

QAlgorithms.Papers.Independent.Intakethird100.P35.maxPathCount

For natural numbers $n,r$, a type $E$ equipped with a finite enumeration of all its elements, a graph $G$ assigning each edge distinct endpoints in $V=\{0,\ldots,n-1\}$, and terminal maps $s,t:\{0,\ldots,r-1\}\to V$, let $p_i$ be the number of the following paths from $s_i$ to $t_i$: choose a length $d$ with $0\le d<n$, an injective vertex sequence $v_0,\ldots,v_d$ beginning at $s_i$ and ending at $t_i$, and an edge sequence $e_0,\ldots,e_{d-1}$ such that each $e_j$ joins $v_j$ and $v_{j+1}$ in either orientation. Different edge labels give different paths even when their endpoints agree. The defined value is $\max_i p_i$, with value $0$ when $r=0$. A disconnected pair has count $0$, while coincident terminals have exactly the length-zero path. No simplicity assumption on $G$ is imposed. The case $n=0$ is included whenever the terminal maps exist, which requires $r=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.netSourceOutflow

For any natural number $n$, any type $E$ equipped with a finite enumeration, any graph with endpoint functions $\ell,r:E\to\{0,\ldots,n-1\}$ satisfying $\ell(e)\ne r(e)$, any function $f:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$, and any vertex $v\in\{0,\ldots,n-1\}$, write $f_e^0=f(e,\mathrm{false})$ and $f_e^1=f(e,\mathrm{true})$. The defined real number is

$$\sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}(f_e^0-f_e^1) +\mathbf 1_{\{r(e)=v\}}(f_e^1-f_e^0) \right),$$

where each indicator is $1$ when its condition holds and $0$ otherwise. The values of $f$ may be arbitrary real numbers. If $E$ is empty, the sum is $0$; if $n=0$, there is no vertex $v$ to supply.

QAlgorithms.Papers.Independent.Intakethird100.P35.optimizedLP

For any natural number $n$, types $I,E,D$ with specified finite enumerations, a graph $G$ whose edges $a\in E$ have distinct endpoints $L(a),R(a)\in\{0,\ldots,n-1\}$, functions $s,t:I\to\{0,\ldots,n-1\}$, a function $a:D\to E$, real values $C_d$, and Booleans $\alpha,\beta$ corresponding respectively to independent and hasSlack, this definition constructs a row list and an objective coefficient function on

$$X=\bigl((I\times E\times\{0,1\})\sqcup D\bigr)\sqcup\{\ast\}.$$

For any assignment $x:X\to\mathbb R$, write $f_i(e,b)=x(i,e,b)$, $y_d=x(d)$, $\sigma=x(\ast)$, and define

$$U_x(e)=\sum_{d\in D}\mathbf1_{a(d)=e}C_dy_d,\qquad D_i^x(v)=\sum_{e\in E}\left( \mathbf1_{L(e)=v}(f_i(e,0)-f_i(e,1)) +\mathbf1_{R(e)=v}(f_i(e,1)-f_i(e,0)) \right).$$

For a real-valued function $F$ of assignments, let $R(F,b,\varepsilon)$ denote the stored row with coefficient $F(\delta_j)$ at coordinate $j\in X$, right-hand side $b$, and Boolean equality flag $\varepsilon$, where $\delta_j$ is $1$ at $j$ and $0$ elsewhere. The row list concatenates the following blocks in exactly this order, enumerating every index once within each block: $R(-f_i(e,b),0,\mathrm{false})$ for every $(i,e,b)$; $R(-y_d,0,\mathrm{false})$ for every $d$; $R(y_d,1,\mathrm{false})$ for every $d$; the single row $R(\sum_dy_d,1,\mathrm{true})$; $R(F_{i,v},0,\mathrm{true})$ for every $(i,v)$, where $F_{i,v}(x)=D_i^x(v)$ if $v\ne s_i$ and $v\ne t_i$, and $F_{i,v}(x)=0$ otherwise; then, if $\alpha$ is true, $R(f_i(e,0)+f_i(e,1)-U_x(e),0,\mathrm{false})$ for every $(i,e)$, or, if $\alpha$ is false, $R(\sum_i(f_i(e,0)+f_i(e,1))-U_x(e),0,\mathrm{false})$ for every $e$; finally, if $\beta$ is true, $R(\sigma-D_i^x(s_i),0,\mathrm{false})$ for every $i$, or, if $\beta$ is false, the single row $R(\sigma,0,\mathrm{true})$. Its objective coefficient at $j$ is $\delta_j(\ast)$ when $\beta$ is true and $\sum_iD_i^{\delta_j}(s_i)$ when $\beta$ is false. These are stored coefficients and flags; the definition itself specifies no feasibility relation or optimization direction. There is no simplicity assumption on $G$, no requirement that $s_i\ne t_i$, and no sign requirement on $C_d$. Empty index types are allowed whenever the supplied functions exist: empty indexed blocks disappear and empty sums are zero; in particular, if $D$ is empty, the normalization block remains a row with every coefficient zero, right-hand side $1$, and equality flag true.

QAlgorithms.Papers.Independent.Intakethird100.P35.pathCount

For any natural number $n$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, and any vertices $s,t$, the defined natural number is the cardinality of the finite collection of all data consisting of a length $l<n$, pairwise distinct vertices $v_0,\ldots,v_l$ with $v_0=s$ and $v_l=t$, and edge labels $e_0,\ldots,e_{l-1}$ such that each $e_j$ has endpoints $v_j,v_{j+1}$ in either order. Different choices of edge labels count separately even when their endpoint sequences agree. Length $0$ is included, so the count is $1$ when $s=t$; when $E$ is empty and $s\ne t$, it is $0$. Supplying the terminal vertices excludes $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.roundedCopies

For any type $E$, any function $c:E\to\mathbb R$, natural numbers $m,k,N$, and edge $e\in E$, the number of rounded copies is $\lfloor (mkN)c(e)\rfloor_{\mathbb N}$, where the natural-number product $mkN$ is converted to a real number before multiplication by $c(e)$, and $\lfloor x\rfloor_{\mathbb N}$ is the greatest natural number at most $x$ when $x\ge0$, and is $0$ when $x<0$. No finiteness assumption on $E$ or nonnegativity assumption on $c$ is imposed. In particular, the result is $0$ if any of $m,k,N$ is zero, or if $c(e)\le0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.singlePairFlowValue

For any natural number $n$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, any function $c:E\to\mathbb R$, and any vertices $s,t$, define, for a function $f:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$,

$$D_f(v)=\sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}\bigl(f(e,\mathrm{false})-f(e,\mathrm{true})\bigr) +\mathbf 1_{\{r(e)=v\}}\bigl(f(e,\mathrm{true})-f(e,\mathrm{false})\bigr) \right).$$

The defined value is the real supremum of the set of numbers $D_f(s)$ obtained from functions $f$ satisfying $f(e,b)\ge0$ for every edge and Boolean $b$, $f(e,\mathrm{false})+f(e,\mathrm{true})\le c(e)$ for every edge, and $D_f(v)=0$ whenever $v\ne s$ and $v\ne t$. The vertices $s,t$ may coincide. Capacities need not be nonnegative; if any capacity is negative, the set is empty, whose real supremum here is $0$. If $E$ is empty, the value is $0$. Supplying $s,t$ excludes $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.steinerValue

For a natural number $n$, a type $E$ equipped with a finite enumeration, a graph $G$ assigning each edge distinct endpoints $\ell(e),\rho(e)\in V=\{0,\ldots,n-1\}$, any real-valued capacity function $c:E\to\mathbb R$, and a finite terminal set $S\subseteq V$, the defined value is the real infimum of all numbers $\sum_{e\in E}c(e)\mathbf1_{\text{exactly one of }\ell(e),\rho(e)\text{ belongs to }A}$ as $A$ ranges over subsets of $V$ for which there exist $s,t\in S$ with $s\in A$ and $t\notin A$. Thus, when $|S|\ge2$, it is the minimum of this finite, nonempty collection of cut sums. Every crossing edge label is counted separately, and capacities may be negative. When $|S|<2$, there are no qualifying subsets, and the total real infimum of the empty set is $0$; this includes $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.sumPathCount

For natural numbers $n,r$, a type $E$ equipped with a finite enumeration of all its elements, a graph $G$ assigning each edge distinct endpoints in $V=\{0,\ldots,n-1\}$, and terminal maps $s,t:\{0,\ldots,r-1\}\to V$, the defined value is $\sum_{i=0}^{r-1}p_i$. Here $p_i$ counts all choices of a length $d$ with $0\le d<n$, an injective vertex sequence $v_0,\ldots,v_d$ with endpoints $s_i,t_i$, and an edge sequence $e_0,\ldots,e_{d-1}$ in which each edge joins the corresponding consecutive vertices in either orientation. Paths using different edge labels are counted separately even if those edges have identical endpoints. A disconnected pair contributes $0$, and coincident terminals contribute the single length-zero path. No simplicity assumption is imposed, and repeated terminal pairs at different indices are counted repeatedly. If $r=0$, the sum is $0$; $n=0$ is allowed when the terminal maps exist, necessarily with $r=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.totalValue

For any natural numbers $n,r$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, any function $c:E\to\mathbb R$, and any terminal functions $s,t:\{0,\ldots,r-1\}\to\{0,\ldots,n-1\}$, define

$$D_{f_i}(v)=\sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}\bigl(f_i(e,\mathrm{false})-f_i(e,\mathrm{true})\bigr) +\mathbf 1_{\{r(e)=v\}}\bigl(f_i(e,\mathrm{true})-f_i(e,\mathrm{false})\bigr) \right).$$

The defined value is the real supremum of all numbers $\sum_{i=0}^{r-1}D_{f_i}(s(i))$ arising from families $f_i:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$ such that every $f_i(e,b)\ge0$, every edge satisfies $\sum_{i=0}^{r-1}(f_i(e,\mathrm{false})+f_i(e,\mathrm{true}))\le c(e)$, and $D_{f_i}(v)=0$ whenever $v\ne s(i)$ and $v\ne t(i)$. Terminal vertices may coincide, and their net outflows need not be nonnegative. Negative edge capacities make the set empty, whose real supremum here is $0$. The value is also $0$ when $r=0$ or $E$ is empty. If $n=0$, the supplied graph and terminal functions require $E$ to be empty and $r=0$.

QAlgorithms.Papers.Independent.Intakethird100.P35.worstValue

For any natural numbers $n,r$, any type $E$ equipped with a finite enumeration, any graph with distinct endpoints $\ell(e),r(e)\in\{0,\ldots,n-1\}$, any function $c:E\to\mathbb R$, and any terminal functions $s,t:\{0,\ldots,r-1\}\to\{0,\ldots,n-1\}$, define

$$D_{f_i}(v)=\sum_{e\in E}\left( \mathbf 1_{\{\ell(e)=v\}}\bigl(f_i(e,\mathrm{false})-f_i(e,\mathrm{true})\bigr) +\mathbf 1_{\{r(e)=v\}}\bigl(f_i(e,\mathrm{true})-f_i(e,\mathrm{false})\bigr) \right).$$

The defined value is the real supremum of the set of $z\in\mathbb R$ for which there exists a family $f_i:E\times\{\mathrm{false},\mathrm{true}\}\to\mathbb R$ satisfying $f_i(e,b)\ge0$ for every $i,e,b$, $\sum_{i=0}^{r-1}(f_i(e,\mathrm{false})+f_i(e,\mathrm{true}))\le c(e)$ for every edge, $D_{f_i}(v)=0$ whenever $v\ne s(i)$ and $v\ne t(i)$, and $z\le D_{f_i}(s(i))$ for every $i<r$. Terminals may coincide, and no nonnegativity condition is imposed on $z$. Any negative edge capacity makes this set empty. When $r=0$ and all capacities are nonnegative, the conditions on $z$ are vacuous, so the set is all of $\mathbb R$; the real supremum operation used here returns $0$ for both empty sets and sets unbounded above. Consequently the value is $0$ when $r=0$, and it is also $0$ when $E$ is empty. If $n=0$, the supplied graph and terminal functions require $E$ to be empty and $r=0$.