Lemmas

content: \textbf{DNSP Lemma} Suppose a node in an oriented graph $G \in \mathcal{O}$ does not satisfy DNSP. Then this node will be a Seymour vertex. \label{DNSP_lma}
proof:
label: DNSP Lemma

content: Assume that in an oriented graph $G$, the node $v_0$ has an out-degree of 3. Additionally, suppose that in the induced subgraph of $v_0$'s out-neighbors, every neighbor has an out-degree of 1. Then the out-degree of $v_0$ or one of its neighbors will be a Seymour vertex.
proof: Assume $|N^+(v_0)|=3$. Let $v_{1,1}, v_{1,2}, v_{1,3}$ be the out-neighbors of $v_0$. For each $v_i \in \{v_{1,1},v_{1,2},v_{1,3}\}$, $|N^+(v_i)|\geq 3$. Let $G[v_{1,1},v_{1,2},v_{1,3}]$ represent the induced subgraph by $v_{1,1},v_{1,2},v_{1,3}$.

If any of $v_{1,1}, v_{1,2}, v_{1,3}$ have an out-degree $>$ 3, $v_0$ will have a larger second out-neighborhood than its first. This results in a Seymour vertex. Therefore, assume that all three nodes have an out-degree of exactly 3 in $G$, $|N^+(v_i)|=3$.

This reduces the situation to Case 3 in Lemma \ref{lowdeg} (Minimum Out-Degree $<$ 3), where $v_{1,1}$ acts similarly to $v_0$. There is at most one arc between $v_{2,4}$ and $v_{2,5}$. Here, $v_{2,4}$ will have three out-neighbors, $v_{3,6}, v_{3,7}$, and $v_{3,8}$, with $v_{2,4}$ having degree zero in $G[v_{2,4}, v_{2,5}]$. Then $|N^+(v_{2,4})|=3$ because the MDN has degree 3. These three neighbors of $v_{2,4}$ are second out-neighbors of $v_{1,1}$, giving $|N^{++}(v_{1,1})|=3$. Thus, we have the following equality, $|N^{++}(v_{1,1})|=|N^+(v_{1,1})|=3$.

Hence, $v_{1,1}$ must be a Seymour vertex, contradicting the assumption that such a node could not exist in an MCE.
label: Deg 3 Traversal

content: For any finite, connected oriented graph $G \in \mathcal{O}$ and root vertex $u \in V(G)$, there exists a unique Well-Ordering of V(G) induced by a breadth-first search (BFS) algorithm combined with a lexicographical tie-breaking rule.
proof: Let $G$ be an assumed graph. Define $v_1 \prec v_2$ if $\text{dist}(v_0, v_1) < \text{dist}(v_0, v_2)$ OR $\text{dist}(v_0, v_1) = \text{dist}(v_0, v_2)$ AND $label(v_1) < label(v_2)$. Since the vertex set $V(G)$ is finite, any relation that is total, transitive, and anti-symmetric is by definition well-ordering. These rules provide a strict, unique rank for every node, $V(G)$ is well-ordered under $\prec$.
label: BFS Coordinate System

content: Suppose that the MDN $v_0$ in the oriented graph $G$ has an out-degree less than 3. Then $v_0$ is a Seymour vertex. \label{lowdeg} \end{lemma}
proof: Consider the cases where $N^+(v_0)=0$, $1$, and $2$.

\textbf{Case 1:} Assume that $|N^+(v_0)|=0$ and $v_0$ has no out-neighbors. Since $v_0$ has no out-neighbors, it also has no second out-neighbors, i.e. $|N^{++}(v_0)|=0$. This implies that $|N^{++}(v_0)| = |N^+(v_0)|$, which will make $v_0$ a Seymour vertex.

\textbf{Case 2:} Assume The out-neighborhood of $v$ is a singleton set, $N^+(v_0)=v_{1,1}$. Because $v_0$ is an MDN, the out-degree of $v_{1,1}$ must be at least 1. This neighbor cannot be $v_0$ since this graph is oriented and $v_0 \to v_{1,1} \in V(G)$. Then, this out-neighbor of $v_{1,1}$, $v_{2,2}$, must be a second out-neighbor of $v_0$. Thus, $|N^{++}(v_0)| \geq 1$. This makes $|N^{++}(v_0)| \geq |N^+(v_0)|$ and $v_0$ a Seymour vertex.

\textbf{Case 3:} Assume that the vertex $v_0$ has an out-degree of 2, denoted by $|N^+(v_0)| = 2$, indicating that $v_0$ has exactly two unique out-neighbors. Call these out-neighbors of $v_0$, $v_{1,1}$, and $v_{1,2}$. Then $|N^+(v_{1,1})| \geq 2$ and $|N^+(v_{1,2})| \geq 2$ since $v_0$ is an MDN. Consider the induced subgraph $G[v_{1,1},v_{1,2}]$. At most one arc can exist in an oriented graph of size 2 because oriented graphs do not allow for symmetric arcs. This means there is at most one arc between $v_{1,1}$ and $v_{1,2}$ in $G[v_{1,1},v_{1,2}]$. This leads to $v_{1,1}$ or $v_{1,2}$ having at least two arcs outside of $G[v_{1,1},v_{1,2}]$. Neither $v_{1,1}$ nor $v_{1,2}$ can relate to $v_0$ since $G$ is an oriented graph and $v_0 \to v_{1,1} \in E(G)$ and $v_0 \to v_{1,2} \in E(G)$. Define the nodes $v_{2,3}$ and $v_{2,4}$ as the two out-neighbors of $v_{1,1}$ not in $\{v_0, v_{1,1}, v_{1,2} \}$. This means $v_0$ has $v_{2,3}$ and $v_{2,4}$ as second neighbors. Hence, $v_0$ will have at least two second out-neighbors. Thus $|N^{++}(v_0)| \geq 2$ and $|N^{++}(v_0)| \geq |N^+(v_0)|$, and $v_0$ is a Seymour vertex.

Therefore, in all cases, $v_0$ is a Seymour vertex when its minimum out-degree is less than 3.
label: Too Low

content: Suppose $G \in \mathcal{O}$ with minimum out-degree 3 and a MDN $v_0$. Suppose also that at least one of $v_0$'s out-neighbors has out-degree 0 in its neighbor-induced subgraph. Then $v_0$ is a Seymour vertex.
proof: Assume $|N^+(v_0)|=3$, and let $v_{1,1}, v_{1,2}, v_{1,3}$ be the out-neighbors of $v_0$. Consider the neighbor-induced subgraph $G[v_{1,1}, v_{1,2}, v_{1,3}]$.

Assume that $v_{1,1}$ has out-degree 0 in $G[v_{1,1}, v_{1,2}, v_{1,3}]$. Thus $v_{1,1} \to v_{1,2} \notin G[v_{1,1}, v_{1,2}, v_{1,3}]$ and $v_{1,1} \to v_{1,3} \notin G[v_{1,1}, v_{1,2}, v_{1,3}]$. Since $v_0$ is a MDN with out-degree 3, $v_{1,1}$ must have out-degree at least 3. So $v_{1,1}$ must connect to at least 3 out-neighbors outside of $\{v_{1,1}, v_{1,2}, v_{1,3}\}$. Since $v_0 \to v_{1,1} \in E(G)$, $v_{1,1} \to v_0 \notin E(G)$ by the oriented property of $G$. Thus, $v_{1,1}$ must connect to at least three other nodes $v_{2,4}, v_{2,5}, v_{2,6}$. So, we have $|N^+_G(v_{1,1})| \geq 3$. The nodes $v_{2,4}, v_{2,5}, v_{2,6}$ are not in $G[v_{1,1}, v_{1,2}, v_{1,3}]$ and are not equal to $v_0$, so they are outside $G[v_0, v_{1,1}, v_{1,2}, v_{1,3}]$.

First out-neighbors of $v_{1,1}$ are second out-neighbors of $v_0$. We have that $|N^{++}_{G}(v_0)| \geq 3$.This simplifies to $|N^{++}(v_0)| \geq |N^+(v_0)|$. In other words, $v_0$ is a Seymour vertex. This contradicts the assumption that such a node could not exist in an MCE.
label: Lone Wolf

content: Let $u_i \in R_i$ and let $v_{i+1} \in R_{i+1}$ with $u_i \to v_{i+1}$. Then the out-neighborhood of $ v_{i+1}$ admits the disjoint partition $$N^+( v_{i+1}) = \text{back}(u_i, v_{i+1}) \;\dot{\cup}\; \text{int}( u_i, v_{i+1}) \;\dot{\cup}\; \text{ext}( u_i, v_{i+1}).$$ \end
proof: Every out-neighbor of $ v_{i+1}$ lies in exactly one rooted neighborhood. Arcs may point only to vertices in layers $R_j$ for $j < i$ , $R_{i}$, $R_{i+1}$, or $R_{i+2}$. Thus any $x \in N^+( v_{i+1})$ lies in one of these layers.

1. If $x \in R_j$ for $j < i+1$, then $x \in \text{back}(u_i, v_{i+1})$.
2. If $x \in R_{i+2}$, then $x \in \text{ext}( u_i, v_{i+1})$.
3. If $x \in R_{i+1}$, then $x \in \text{int}( u_i, v_{i+1})$. These sets are clearly disjoint and cover all of $N^+( v_{i+1})$.

label: Degree Partition

content: Let $G \in \mathcal{O}$ be an oriented graph. If every vertex $u \in V(G)$ is DNSP, then it’s out-neighborhood is a minimal set cover by the interior neighborhoods of its children: $$N^+(u) = \bigcup_{v \in N^+(u)} \text{int}(u, v)$$
proof: Let $x \in N^+(u)$. By assumption, there exists $v \in N^+(u)$ such that $v \to x \in G$. Then $x \in N^+(v)$, and hence $x \in \text{int}(u,v)$. Since $x$ was arbitrary, we have $$ N^+(u) \subseteq \bigcup_{v \in N^+(u)} \text{int}(u,v). $$ Conversely, for any $x \in \text{int}(u,v)$ with some $v \in N^+(u)$, we have $x \in N^+(u)$ by definition. Thus, $$ \bigcup_{v \in N^+(u)} \text{int}(u,v) \subseteq N^+(u). $$ Combining both inclusions, we conclude $$ N^+(u) = \bigcup_{v \in N^+(u)} \text{int}(u,v). $$ Suppose the cover is not minimal. Then at least one subset is redundant. This implies that there exists an arc $v \to w \in \text{int}(u, v)$ that does not perform load balancing on $u$. This proves the minimal set cover. This is a minimum inclusion-wise, as no interior neighbor sets can be removed.
label: Load-Balance Theorem

content: Let $G \in \mathcal{O}$ be an oriented graph where every vertex is DNSP. For any vertex $u \in V(G)$, the subgraph induced by its out-neighborhood $N^+(u)$ contains at least one directed cycle.
proof:
label: Interior Cycles Lemma

content: Let $G \in \mathcal{O}$ be an oriented graph where every vertex $u_k \in R_k$ is DNSP, then this structure cannot be a BFS tree or forest.
proof:
label: Graph Level Order vs BFS

content: Let $G \in \mathcal{O}$ be an oriented graph where every vertex is DNSP. For any $u \in R_i$, the second out-neighborhood is the maximal union of the exterior neighborhoods of its children: $$N^{++}(u) = \left( \bigcup_{v \in N^+(u)} \text{ext}(u,v) \right) \cup \left( \bigcup_{v \in N^+(u)} \text{back}(u, v) \right).$$
proof: To establish the equality $N^{++}(u) = \left( \bigcup \text{ext}(u,v) \right) \cup \left( \bigcup \text{back}(u, v) \right)$, we show containment in both directions.

Forward Inclusion ($\subseteq$): Let $x \in N^{++}(u)$. By definition, there exists a path $u \to v \to x$. Since $u \in R_i$, its neighbor $v$ must be in $R_{i+1}$. By the properties of rooted layering, any neighbor $x$ of $v$ must lie in $R_j$ where $j \le (i+1) + 1 = i+2$. Because $x$ is a second neighbor of $u$, it cannot lie in $N^+(u) = R_{i+1}$, nor can it be $u$ itself. Thus, $x$ must either lie in $R_{i+2}$ or in some layer $R_j$ with $j < i$. If $x \in R_{i+2}$, then $x \in \text{ext}(u,v)$. If $x \in R_j$ for $j < i$, then $x \in \text{back}(u, v)$. In either case, $x$ is contained in the union of the children's exterior and back neighborhoods.

Reverse Inclusion ($\supseteq$): Let $x$ be a back node of some child $v \in N^+(u)$. There exists a path $u \to v \to x$. Since $x$ is in a layer prior to $R_i$, it cannot be in $N^+(u)$ or be $u$ itself. Thus, $x \in N^{++}(u)$. Let $x$ be an exterior neighbor of some child $v \in N^+(u)$. There exists a path $u \to v \to x$ where $x \in R_{i+2}$. Since $R_{i+2}$ is disjoint from $R_{i+1}$ and $R_i$, $x$ is neither a neighbor nor the parent, meaning $x \in N^{++}(u)$. Combining these, we conclude that the second neighborhood is precisely the union of these two sets.
label: Reduction Theorem

content: Every oriented graph $G = (V,E)$ can be represented by a Graph Level Order.
proof:

1. \textbf{Select a minimum out-degree root}. Select a vertex $v_0 \in V$ of minimum out-degree to serve as the root. Let $$ R_0 = \{v_0\}. $$
2. \textbf{Define rooted neighborhoods}. For each $i \ge 1$, define $$ R_i = \{ u_i \in V : \text{dist}(v_0, u_i) = i \}, $$ where $\text{dist}(v_0, u_i)$ is the shortest directed path length from $v_0$ to $u_i$. These sets form a finite sequence of disjoint neighborhoods covering $V$.
3. \textbf{Partial order on neighborhoods}. For $u_i \in R_i$ and $v_j \in R_j$ with $i < j$, $v_j$ is further from the root than $u_i$. Arcs from $R_j$ to $R_i$ may exist but don't interfere with the BFS layer or parent-child structure. Hence, the neighborhoods form a natural level order $R_0 < R_1 < \cdots < R_k$.
4. \textbf{Total order within neighborhoods}. Within each $R_i$, impose a consistent total order on vertices (e.g., lexicographic or by degree). Together with the neighborhood order, this defines a universal vertex order compatible with the BFS-layered structure.
5. \textbf{Parent–child relations}. For $u_i \in R_i$ and $v_{i+1} \in R_{i+1}$, if $u_i \to v_{i+1} \in E$, declare $u_i$ a parent and $v_{i+1}$ a child. This defines parent-child relationships between levels.
6. \textbf{Interior and exterior neighbors}. For a parent-child pair $u_i \to v_{i+1}$: $$ \text{int}(u_i,v_{i+1}) = N^+(u_i) \cap N^+(v_{i+1}) \cap R_{i+1}, \quad \text{ext}(u_i,v_{i+1}) = N^{++}(u_i) \cap N^+(v_{i+1}) \cap R_{i+2}. $$

label: Graph Level Order Representation of Oriented Graphs

content: In any Graph Level Order that maximizes DNSP nodes, the density cost of an arc is defined as $\Delta D = \frac{|E|}{|V|}$.

1. A Forward Arc $v_i \to v_{i+1}$ increases $|E|$ by 1 and $|V|$ by 1, maintaining a linear growth rate.
2. A Back-Arc $v_i \to u_j$ increases $|E|$ by 1 while keeping $|V|$ constant. proof:
   label: Density Dominance of Forward Arcs
   

content: In any Graph Level Order representation of $G$, let $u_i$ be the node in $G$ with the first back arc and assume that all interior neighbors of $u_i$ are Seymour. Then the first back arc of $u_i$ will make $u_i$ an overall Seymour vertex immediately or introduce a chain of children making one of them Seymour.
proof: Case 1: $u_i$ has no children with back arcs to $N^+(v_j)$.

If $u_i$ has no children with back arcs to $N^+(v_j)$, then $N^+(u_i)$ consists only of the back-arc and interior neighbors. The DNSP check is local. The back-arc $u_i \to v_j$ adds the entire out-neighborhood of $v_j$ to $N^{++}(u_i)$. Because this is the first back-arc, $v_j$ is closer to the root, its exterior degree is larger. Without children to absorb these neighbors through transitive triangles, $N^+(v_j) \subseteq N^{++}(u_i)$. This forces $|N^{++}(u_i)| \geq |N^+(v_j)|$. Since neighborhood sizes shrink as distances increase in a DNSP graph ($|R_i| < |R_j|$), $u_i$ cannot sustain this. It becomes an immediate Seymour vertex.

Case 2: $u_i$ has children that overlap with $N^+(v_j)$.
If $u_i$ does have children ($u_{i+1} \in R_{i+1}$), then $u_{i+1} \to v_{j+1}$, where $u_i \to u_{i+1}$ and $v_j \to v_{j+1}$.
For $u_i$ to remain DNSP, there must be enough nodes covered by these children to reduce the size of $u_i$'s second neighborhood below its first.
Since these nodes $v_{j+1}$ are in an early level ($R_j$ or $R_{j+1}$) and $u_{i+1}$ is in a late level ($R_{i+1}$), the child $u_{i+1}$ is now forced to have its own back-arc to $v_{j+1}$.

This produces a finite descending chain of obligation.
Once a back arc is introduced, it either immediately fails the DNSP (Case 1) or exports the density requirement to a children in $R_{i+1}$
By forcing it onto its children, they face the same dilemma in a layer with fewer nodes. This chain can (at most) continue until it hits a level with no more children (a sink). At that sink, Case 1 will inevitably trigger.

Because the Graph Level Order levels $\{R_0, R_1, \dots, R_k\}$ are finite and strictly ordered, this chain must eventually terminate at a leaf node $u_{sink} \in R_{max}$. At this boundary, the inductive offloading of Case 2 is impossible, and Case 1 triggers, creating a Seymour vertex.

To prevent $u_i$ from immediately becoming a Seymour vertex (Case 1), back arcs are forced to be introduced in $N^+(u_i)$ (Case 2). This creates a terminating chain of back-arcs that must spread to the sink at $R_{max}$. At $R_{max}$, the DNSP fails, proving that the assumption of a first back-arc leads to a contradiction.
label: Back Arcs Problem

content: Let \(G \in \mathcal{O}\) be an MCE to the SSNC. Then \(G\) contains no back arcs.
proof: We use the definition of \(G\) as a minimal counterexample to demonstrate this through contradiction. The node \(x \in V(G)\) fulfills the DNSP: \(|N^{++}(x)| < |N^{+}(x)|\). Assume, for contradiction, that \(G\) contains a back arc \(e = (u, v)\) where \(u \in R_i, v \in R_{j}, j < i\). According to Theorem \ref{red} (Reduction), any second neighbor can be expressed as a union of the exterior neighbors and back arcs of $u$. The reachability provided by the back arc \(e\) to any subsequent node \(w \in N^{++}(u)\) is already covered by forward arcs established by the rooted neighborhoods. To utilize this back arc, $u$ had to choose it over a forward arc $e'$. Any back arc $e=(u,v)$ can be replaced by some forward arc $e'$ without decreasing any second neighborhoods because $v$ is already reachable via forward paths. Hence $e$ is redundant. Such a forward arc must exist because $u$ begins with out-degree capacity of $\delta$ and the DNSP requires that as the path length increases, the neighborhood size decreases. The first back arc is not possible until rooted neighborhood 2, at which case, the exterior capacity has already decreased by 2 because of DNSP. Following this, the exterior capacity only continues to decrease. This allows for more capacity than can go into the exterior neighbors. Let $G' = G - e \cup e'$. The back arc \(e\) leads to the node \(v\), and any subsequent node \(w \in N^{++}(u)\) is already reached by the shortest path nature of forward arcs. Replacing the unnecessary arc $e$ with $e'$ does not increase any node's second neighborhood size. As a result, $G'$ remains a counterexample, with every node satisfying the DNSP. As $|V(G')|=|V(G)| + 1$ and $|E(G')| = |E(G)|$, $G'$ is a counterexample with equal arcs as \(G\) with a more dense structure. This shows that $G$ is not an MCE.
label: Back Unnecessary

content: Let $G \in \mathcal{O}$ be an MCE to the SSNC.

Let $u_i \in R_i$ and $u_{i-1} \in R_{i-1}$ be a parent of $u_i$.

Define $I_{\mathrm{req}}$ as the minimal number of interior arcs on $u_{i-1} \to u_i$ to ensure a counterexample, $|N^{++}(x)| < |N^{+}(x)|$, for all ancestors $x$ of $u_{i-1}$ are DNSP.

Then, the number of interior arcs equals this minimum required amount: $|\text{int}(u_{i-1}, u_i)| = I_{\mathrm{req}}$.
proof: By Theorem \ref{lbl} (Load-Balance), the only purpose of interior degree is to prevent parents from becoming Seymour vertices. Consider an excess interior arc $e=u_{i-1} \to u_i$ such that $$|\text{int}(u_{i-1}, u_i)| \ge I_{\mathrm{req}} + 1.$$ By the definition of $I_{\mathrm{req}}$, the arc $e$ is not participating in preventing $u_{i-1}$ from being a Seymour vertex. Therefore, the arc $e$ is unnecessary in an MCE and can be removed. The graph $G' = G-e$ is a smaller graph arc-wise where every arc in $R_i$ is still preventing $u_{i-1}$ from being a Seymour vertex. Because $e$ is an interior arc $u_i \to v_i \in R_i$, its removal cannot increase $|N^+(x)|$ for any ancestor. Also, because $e$ is excess, its role in providing paths to $R_{i+1}$ is already covered by the $I_{\mathrm{req}}$ set. Thus, the path cost to any node in $R_{i+1}$ remains unchanged or increases, ensuring $|N^{++}(x)|$ does not grow. Thus $G'$ is a smaller counterexample, contradicting the MCE. We conclude that no excess interior arcs can exist in $G$, and therefore $|\text{int}(u_{i-1}, u_i)|$ must be exactly equal to $I_{\mathrm{req}}$.
label: No Excess Interior Arcs

content: Let $G \in \mathcal{O}$ be an MCE to the SSNC. All nodes in $G$ have out-degree $\delta$.
proof: Let $v_{i+1}$ be the first node with out-degree at least $\delta + 1$ and suppose the interior degrees of its parent are Seymour vertices. By the first, all nodes closer to $v_0$, have an out-degree of $\delta$. If this extra arc $e$ is an interior arc then $G$ is not an MCE by Corollary \ref{noxsint} (No Excess Interior Arcs). Thus, $e$ must be an exterior arc. An extra exterior arc increases the parent's second neighborhood size. The cycle implied by Theorem \ref{lbl} (Load Balance) is to reduce this size by exactly 1. The extra arc $e$ adds that node back, causing the node $u_i$ ($v_{i+1}$'s parent) second neighborhood to be equal in size to its first (i.2 $|R_{i+1}| = |R_{i+2}|$). This makes $u_i$ a Seymour vertex. Thus, we conclude that this node $v_{i+1}$ cannot exist.
label: Regular Graph

content: Let $G \in \mathcal{O}$ be an MCE to the SSNC, and let $R_k$ be a rooted neighborhood at distance $k$. Then every node $v_k \in R_k$ will have an interior out-degree of $k$ in $R_k$.
proof: Since $R_i$ is a rooted neighborhood, all nodes in $R_i$ share the same parents. In particular, $v_{i-1}$ is also a parent of $w_i$. Since $G$ is an MCE, no subgraph of $G$ including the first $i-1$ rooted neighborhoods can be a counterexample. For the parent $v_{i-1}$ not to become a Seymour vertex, every node $w_i \in R_i$ must contribute at least the minimal required capacity: $$|\text{int}(v_{i-1}, w_i)| \ge i.$$ Assume, for contradiction, that $w_i$ has an interior degree greater than $i$. This implies the existence of an excess interior arc $e$ such that $|\text{int}(v_{i-1}, w_i)| \ge i+1$. The existence of such a redundant arc directly contradicts the arc-minimality of $G$. The No Excess Interior Arcs Corollary (\ref{noxsint}) proves that any arc $e$ beyond the necessary minimum $I_{\text{req}}(i)$ can be removed. The graph $G$ would remain a counterexample and $G - e$ is a smaller MCE. Thus, $G$ cannot be an MCE, which is a contradiction. We conclude that $w_i$ cannot have an excess arc, and its interior degree must be exactly $i$: $$|\text{int}(v_{i-1}, w_i)| = i.$$ The conclusion holds for all nodes in the rooted neighborhood $R_i$. The nodes are forced to be indistinguishable by the constraints. Further, all nodes in $R_i$ have the interior degree $i$ and $I_{\text{req}}(i) = i$.
label: Regular Interior Degrees

content: The only possible transitive triangles in an MCE are load-balancing triangles.
proof: We classify all transitive triangles by examining the first two arcs and determine whether a valid third arc can close the triangle transitively.

1. Intra-layer arc: both endpoints in the same rooted neighborhood $R_i$ ($R_i \to R_i$).
2. Forward arc: from parent to child ($R_i \to R_{i+1}$).
3. Back arc: from a vertex in $R_j$ to one in a lower-level neighborhood $R_i$, $ j < i$. <\ol> A triangle has three arcs, so there are $2^3 = 8$ possible combinations of arc types. We enumerate these cases in Table \ref{transtricases}: No2F1B

   Case	Labels	Triangle Possible	Reason
   1	3I	Yes	(all Intra-layer)
   2, 4	1B2I / 1F2I	Symmetric Arcs
   3	2B1I	Yes	$x,y \in R_i$, $z \in R_{i+1},x \to y,z \to x,z \to y$
   5	1F1B1I	Yes$x, y \in R_i, z\in R_{i+1}, x \to y,x \to z,z \to y$.
   6	1F2B	Yes	$x \in R_i ,y \in R_{i+1},z \in R_{i+2},x \to y$,$z \to x$,$z \to y$.
   7	2F1I	Yes	$x\in R_i,y,z \in R_{i+1},x \to y, x \to z, y \to z$.
   8	No	cannot form a closed transitive triangle.

   Combinations of intra-layer, forward, and back arcs forming transitive triangles. From these 8 possible cases, three are excluded immediately because of impossibility (Cases 2, 4, 8). Theorem \ref{backbad} (Back Arcs Problem) says that an MCE seeks to maximize DNSP nodes and eliminates triangles that rely on a back arc (Cases 3, 5, and 6). The remaining triangles are the following: Case 1: $x \to y \to z \to x$, all in $R_i$, and the Load-Balancing Triangle (Case 7). Assume an MCE $G$ contains a triangle from Case 1. Because such a triangle is not a load-balancing triangle, it must contain an extra interior arc. By Corollary \ref{noxsint} (No Extra Interior Arcs), removing this arc yields a smaller MCE, contradicting the minimality of $G$. Load-Balancing Triangle is the only remaining case. These are a necessary structure to satisfy DNSP for the parent. Consider also transitive triangles with two parents connecting to one child in the next rooted neighborhood. This type of triangle will not be eliminated, though, because this is still a load-balancing triangle in a Graph Level Order. Thus, only the load-balancing triangles survive the MCE constraints.
   label: Load-Balancing Triangles
   

content: Let $G \in \mathcal{O}$ be a Graph Level Order containing a Seymour diamond. Then the ambiguity is resolved via exterior neighbors.
proof: Assume we have a Seymour diamond $u_i, v_{i+1}, w_{i+1},y_{i+2}$. Theorem \ref{red} (Reduction) gives the following equality: $N^{++}(u_i) = \bigcup_{v_{i+1} \in {N^+(u_i)}} \text{ext}(u_i, v_{i+1})$. For a Seymour diamond, this resolves to $$|N^{++}(u_i)| = |\left( \bigcup_{v \in N^+(u)} \text{ext}(u,v) \right) \cup \left( \bigcup_{v \in N^+(u)} \text{back}(v) \right)|.$$ By Theorem \ref{backbad} (Back Arcs Problem), the back arcs part of this equality can be removed, and we are left with $$|N^{++}(u_i)| = |\bigcup_{v \in N^+(u)} \text{ext}(u,v)| = |\{y_{i+2}\}|.$$ Because the exterior neighbors are sets, any node reached by multiple length-2 paths is counted only once in $N^{++}(u_i)$, eliminating double-counting. for the node $u_i$. Therefore, the proof is complete.
label: Resolution of Seymour Diamonds

content: In any oriented graph, without back arcs, the minimum out-degree node \( v_0 \) within a Graph Level Order structure provides a well-ordering, enabling an inductive analysis of all other nodes in the graph.
proof: First, remember that we are under the assumption that we do not have back arcs.
We have already shown that under this assumption, the rooted neighborhoods in a Graph Level Order form a total order. Further, they are a discrete total order.
By definition, a set is considered well-ordered if every non-empty subset of that set has a least element.
A discrete total order is a total order, where each element has a distinct next element in the order.
Since a discrete total order has a clear distinction between elements, any non-empty subset will always have a smallest element according to the order.
This fulfills the condition of being well-ordered.
Every non-empty subset will have a least element, which is the defining characteristic of a well-ordered set.
Thus, the total order defined by the distance from \(v_0\) on the set of rooted neighborhoods \(R_1, R_2, \ldots\) constitutes a well ordering.
label: Graph Level Order Supports Induction

content: Let $G$ be an arc-minimal MCE. Every vertex within a rooted neighborhood $R_k$ is vertex-transitive under the rooted automorphism $\sim$. The resulting quotient graph $G/\sim$ is a well-defined hyper-node graph that preserves the out-degree and DNSP of $G$.
proof: Let $v_k, w_k \in R_k$. By Lemma \ref{nodepartition} (Degree Partition), the degree of every node is partitioned into interior neighbors, exterior neighbors, and back-arcs. By Corollary \ref{regint} (Regular Interior Degrees), both nodes possess identical interior degrees of $k$. Since back arcs are excluded by Theorem \ref{backbad} (Back Arcs Problem), it follows that they possess identical exterior degrees of $\delta - k$. Furthermore, by Corollary \ref{noxsint} (No Excess Interior Arcs), all interior arcs of $v_k$ and $w_k$ must induce forward-facing transitive triangles. As these are the unique load-balancing triangles permitted by Theorem \ref{lbt} (Load-Balancing Triangles), the rooted induced subgraphs $G[R(v_k)]$ and $G[R(w_k)]$ are isomorphic under a neighborhood-preserving automorphism fixing the root. Since this isomorphism holds for all pairs in $R_k$, the set $R_k$ constitutes an equivalence class under automorphism. Collapsing these classes yields a well-defined quotient graph $G / \sim$.
label: Rooted Neighborhood Quotient

content: Let $G \in \mathcal{O}$ be an MCE to the SSNC with $u_k \in R_k$.

In a minimal counterexample to the SSNC, there is a direct trade-off between exterior and interior neighbors.

1. For any parent node $u_k$ at level $k$: Each unit decrease in the exterior neighborhood (vertices in $R_{k+2}$) forces an increase in the interior degree (arcs within $R_{k+1}$).
2. Because these interior arcs connect siblings, they create forward-facing transitive triangles rooted at $u_k$.
3. The total number of these triangles is governed by:$$|T(u_k)| = |R_{k+1}| \cdot (k+1)$$ <\ol>
   proof: Since $G \in \mathcal{O}$ is an MCE, every vertex has an out-degree exactly $\delta$ by Corollary \ref{reggraph} (Regular Graph). Since $u_k \in R_k$, we can partition a child of its $v_{k+1} \in R_{k+1}$. By Lemma \ref{nodepartition} (Degree Partition) and DNSP nodes, we have $$|\text{ext}(u_k, v_{k+1}) \le \delta - k.$$ For every single reduction of the exterior neighborhood of $u_k$, it also loses $1$ neighbor in $R_{k+1}$, making that neighborhood size $|R_{k+1}| - 1$. By Corollaries \ref{noxsint} (No Excess Interior Arcs) and \ref{regint} (Regular Interior Degree), every node is forced to have an interior out-degree of exactly $k+1$. The Load-Balance Theorem \ref{lbl} can be iterated, which says that these children of $u_k$ are a union of the out-neighborhood over the size of these interior degrees. By Rooted Equivalence, all vertices $v \in R_{k+1}$ are indistinguishable. Therefore, any reduction in exterior capacity of the parent $u_k$ must be distributed uniformly across all children. This produces a set of arcs within $R_{k+1}$ for each iteration that correspond to cycles. These cycles can then be accumulated by recording the graph $G' = G - C_{i-1}$, where $C_{i-1}$ is a set of cycles recorded at the last iteration. This procedure is guaranteed to produce a cycle at every iteration because it repeatedly calls the Theorem \ref{lbl} (Load-Balance) on a smaller subgraph. These subgraphs are still regular since exactly one edge is removed from every vertex. Also, these graphs are finite, guaranteeing termination. Finally, the set of cycles returned by this procedure is the set mapped to by the set $T(u_k)$. There are $k+1$ iterations of this procedure, one for every cycle produced by the exterior neighbors. There is also a base case from Theorem \ref{lbl} (Load-Balance). The nodes in $R_{k+1}$ have to cover the out-neighborhood of $u_k$ without any of the arcs from the transitive triangles from the exterior. At the termination of this procedure the total number of forward-facing transitive triangles is $$(k+1) \cdot |R_{k+1}|.$$
   label: Law of Conservation of Neighbors
   

content: Let $G=(V,E)$ be an oriented graph that is an MCE to the SSNC, and let $G$ be represented in a Graph Level Order rooted at a minimum out-degree vertex $v_0$. Let $u_k \in R_k$, and let $$ S:=N^+(u_k) \subseteq R_{k+1}. $$ Then the subgraph induced by $S$, denoted $G[S]$, can be decomposed into edge-disjoint directed cycles by an iterative load-balancing process. In particular, $G[S]$ contains at least one directed cycle, and repeated cycle removal terminates only when no interior arcs remain.
proof:
label: Iterative Load-Balance

content: $$\begin{aligned} \text{Maximize} \quad & Z(d) = \sum_{E_{\text{fwd}}} f_{uv} + \sum_{E_{\text{int}}} (1-\epsilon) f_{uv} + \sum_{E_{\text{back}}} (1-\epsilon) f_{uv} \\ \text{subject to:} \quad & \sum_{v:(u,v) \in E} f_{uv} - \sum_{v:(v,u) \in E} f_{vu} = \delta_u, \quad & \forall u \in V \\ & \sum _{w\in N^{+}(u),w\ne v}f_{vw}\ge dist(v_0, u) ,\quad \forall u\in V,\forall v\in N^{+}(u) & 0 \le f_{uv} \le 1, \quad \forall (u,v) \in E \end{aligned}$$ Let $G \in \mathcal{O}$ be an MCE to the SSNC. Then $G$ does not have back arcs or extra interior arcs. \end{theorem}
proof: Let $G=(V,E)$ be a feasible solution of the hyper-node LP with objective value $Z$.

Consider any arc $e \in E$ that is either a back arc or an extra interior arc not required for load balancing.

Case 1: The Back-Arc Elimination ($R_i \to R_j, j < i$)

A back-arc $e = u \in R_i \to v \in R_j $ exists in the Graph Level Order. This arc carries a cost of $1-\epsilon$. Because the primal objective maximizes $Z(d)$, the Simplex method identifies this back-arc as a High-Cost Slack Variable. The graph's connectivity allows for a forward path to be used instead and the solver will perform a basis exchange, improving the objective by $\epsilon$. Since an MCE is defined as a minimal counter-example, the existence of a back-arc implies a non-minimal flow state. By maximizing $Z(d)$, the LP optimizes the graph, proving that back-arcs are not a necessary feature for a counterexample.

Case 2: The Redundant Interior Arc ($R_i \to R_i$)

An extra interior arc $e = u_1 \to u_2$ exists in the Graph Level Order. This creates a path through the next layer $R_{i+1}$ using forward arcs only. Replacing the interior arc $(1-\epsilon)$ with a forward arc (of cost 1) again yields the $\epsilon$ improvement.

In both instances, performing a pivot along a cycle, replacing the redundant arc with a forward-facing arc, strictly increases the objective: $Z_{\text{new}} = Z - \epsilon < Z$.

$$Z_{\text{new}} = Z - (1-\epsilon) + 1 = Z + \epsilon > Z,$$ contradicting the assumption that $G$ was an optimal LP solution. Therefore, in any optimal solution of the LP, back arcs or extra interior arcs do not appear. Combined with DNSP constraints, this implies that the optimal LP solutions are precisely the $k$-regular MCEs, with no back arcs or extra interior arcs.
label: Regular Optimality of LP

content: Let $G$ be an oriented graph represented by a Graph Level Order rooted at a minimum out-degree vertex $v_0$ with $|N^+(v_0)|=\delta$.

Let $u_i \in R_i$ and let $v_{i+1} \in N^+(u_i) \cap R_{i+1}$.

Then for every $z \in \mathrm{ext}(u_i,v_{i+1})$,$$|\mathrm{ext}(v_{i+1},z)| < |\mathrm{ext}(u_i,v_{i+1})|.$$
proof: By Theorem \ref{regint} (Regular Interior Degrees), we have $$|\mathrm{int}(u_i,v_{i+1})| = i+1 \quad\text{and}\quad |\mathrm{int}(v_{i+1},z)| = i+2.$$ Since $N^+(v)$ decomposes into interior and exterior neighbors and $|N^+(v)|=\delta$, $$|\mathrm{ext}(u_i,v_{i+1})| = \delta-(i+1), \qquad |\mathrm{ext}(v_{i+1},z)| = \delta-(i+2).$$ As $i+2>i+1$, the claim follows by subtraction.
label: Decreasing Exteriors

content: Let $G \in \mathcal{O}$ be be an MCE with MDN $v_0$, with rooted neighborhoods $R_0, R_1, \dots, R_k$ constructed by layering. Suppose all nodes are DNSP. Then for all $i \ge 0$, $$|\text{ext}(u_i, v_{i+1})| \le |N^+(v_0)| - i\text{ where }u_i \in R_i, v_{i+1} \in R_{i+1}$$
proof: We proceed by induction on $i$. \textbf{Base Case ($i=0$):} The root $R_0 = \{v_0\}$ has out-neighbors $R_1 = N^+(v_0)$, with $|R_1| = |N^+(v_0)|$. Consider $v \in R_1$ and define the exterior set $$\text{ext}(v_0, v) = N^{++}(v_0) \cap N^+(v) \cap R_2.$$ Since $v_0$ is DNSP, $$|N^{++}(v_0)| < |N^+(v_0)| = |N^+(v_0)|,$$ and hence $$|\text{ext}(v_0, v)| \le |N^+(v_0)| - 1.$$ \textbf{Induction Hypothesis:} Assume that for some $i \ge 0$, $$|\text{ext}(u, v)| \le |N^+(v_0)| - i, \quad \forall u \in R_i,\ v \in R_{i+1},\ y \in R_{i+2}.$$ Inductive Step: Consider $u_{i+1} \in R_{i+1}$ and $v_{i+2} \in R_{i+2}$ with $u_{i+1} \to v_{i+2} \in G$. By Corollary \ref{ilb} (Iterative Load-Balance), the interior degrees of nodes along the path from $v_0$ up to $u_{i+1}$ all belong to disjoint cycles. Corollary \ref{del} (Decreasing Exteriors) ensures $$|\text{ext}(u_{i+1}, v_{i+2})| < |\text{ext}(w_i, u_{i+1})|,$$ for any parent $w_i \in R_i$ of $u_{i+1}$. By the induction hypothesis, $$|\text{ext}(w_i, u_{i+1})| \le |N^+(v_0)| - i.$$ Combining these inequalities gives $$|\text{ext}(u_{i+1}, v_{i+2})| < |N^+(v_0)| - i \implies |\text{ext}(u_{i+1}, v_{i+2})| \le |N^+(v_0)| - (i+1).$$ Thus, the bound holds at level $i+1$. By induction, the statement is true for all $i \ge 0$.
label: DNSP Impact on Rooted Neighborhood Size

content: Let $G \in \mathcal{O}$ be an MCE with MDN $v_0$, where $|N^+(v_0)| = \delta$. Suppose all nodes in $G$ are DNSP nodes. Then the rooted neighborhoods $R_i$ satisfy the bounds: $$|R_0| = 1, \quad |R_1| = \delta, \quad |R_i| \le \delta - (i-1) \text{ for } i \ge 2.$$
proof: Base cases: \begin{itemize} \item $R_0 = \{v_0\}$, so $|R_0| = 1$ by definition. \item $R_1 = N^+(v_0)$, so $|R_1| = \delta$. \end{itemize} Inductive hypothesis: Assume that for some $k \ge 1$, $$|R_k| = \delta - (k-1), $$ and that for all $u \in R_k$, the exterior neighbors satisfy $$|\text{ext}(u_{k-1}, u)| \le \delta - (k-1),$$ while interior neighbors satisfy $|\text{int}(u)| \ge k$. Inductive step: Consider $R_{k+1}$. By Corollary \ref{nbhsize} (DNSP Impact on Rooted Neighborhood Size), the number of exterior neighbors along any parent–child edge is strictly decreasing. Therefore, for each $v \in R_{k+1}$, $$|\text{ext}(u_k, v)| \le |\text{ext}(u_{k-1}, u_k)| - 1 \le (\delta - (k-1)) - 1 = \delta - k.$$ Every node in $R_{k+1}$ is counted via some exterior neighbor of a parent in $R_k$. These are all equivalent under Theorem \ref{nbhquot} (Rooted Neighborhood Quotient). So have $$|R_{k+1}| \le \delta - k.$$ By induction, the formula $$|R_i| \le \delta - (i-1), \quad i \ge 2,$$ holds for all rooted neighborhoods.
label: Formula for Rooted Neighborhood Size

content: Let $G \in \mathcal{O}$ be an oriented graph with rooted neighborhoods $R_i$. Let the earliest back arc in $G$ be from a node $u_i \to v_j,u_i \in R_i, v_j \in R_j, j < i$. Then this back arc will produce a Seymour vertex.
proof: All nodes in $G$ are DNSP nodes. Corollary \ref{reggraph}(Regular Graph) says that every node has an out-degree exactly $\delta$. Corollary \ref{ilb} (Iterative Load Balance) shows that the interior degree of every node is Seymour because it is a member of disjoint cycles. When the first back-arc $e=u_i \to v_j$ is introduced, $u_i$ inherits the second neighborhood of an ancestor $v_j$. By Theorem \ref{backbad} (Back Arcs Problem), we know either $|ext(v_{j-1}, v_{j})|>|ext(u_{j-1}, u_{i})|$ due to the strictly decreasing sequence of exteriors in the forward-arc-only prefix, or a child will overlap that exterior set. In the first case, the out-degree of $u_i$ remains $\delta $, but its second neighborhood grows:$$|N^{++}(u_i)_{back}|>|N^{++}(u_i)_{fwd}|.$$ This inheritance forces $|N^{++}(u_i)_{with\_back\_arc}|\ge |N^{+}(u_{i})|$, contradicting the DNSP assumption. In the second case, a chain is produced, that must be finite by the DNSP. It terminates with a node $u_t$ whose interior neighbors double, like those in $u_i$, and whose exteriors violate the Seymour condition like $u_i$. This forces the Seymour condition in $u_t$. $$|N^{++}(u_t)_{back}|\ge |N^{+}(u_{t})|$$ Therefore, no such back arc $e$ can exist in an MCE.
label: No Back Arcs

content: Let $G \in \mathcal{O})$ be an oriented graph with minimum out-degree $\delta \ge 3$. Let $\mathcal{R} = \{R_0, R_1, \dots, R_k\}$ be the rooted neighborhoods of $V$ originating at a root $v_0$ of minimum out-degree. If every $u \in G$ is DNSP, then:

1. The maximum number of rooted neighborhoods is $k = \lceil \frac{\delta} {3} \rceil$.
2. The cardinality of the terminal level set is $|R_k| = \delta - k + 1$.
3. Every node in $R_{k-1}$ will belong to at least $k-1$ disjoint cycles.

proof: Fix $i \ge 1$ and consider the rooted neighborhood $R_i$.

The Regular Interior Degree Corollary \ref{regint} says that every node in $R_i$ must have an interior degree of exactly $i$.

The Iterative Load-Balance Corollary \ref{ilb} converts each node's interior degrees into transitive triangles using the Load-Balance Theorem \ref{lbl}. This results in a requirement of the following-sized set of disjoint interior arcs: \[|R_i| \cdot i \tag{1} \] As an oriented graph itself, the number of arcs in $R_i$ is bounded above by the number of unordered pairs of vertices in $R_i$: \[|E(R_i)| \le \binom{|R_i|}{2}. \tag{2} \] Combining (1) and (2) yields the following feasibility condition: \[|R_i| \cdot i \le \binom{|R_i|}{2} \quad \Longleftrightarrow \quad 2i \le |R_i| - 1. \tag{3} \] Next, by Corollary \ref{nbhsizefmla} (Formula for Rooted Neighborhood Size), DNSP nodes enforces a global contraction of neighborhoods: \[|R_i| \le \delta - (i - 1).\tag{4}\] Substituting (4) into (3) gives \[2i \le \delta - i \quad \Longleftrightarrow \quad 3i \le \delta. \tag{5} \] Thus, for any rooted neighborhood $R_i$ to exist without forcing Seymour vertices, it is necessary that $$ i \le \frac{\delta} {3}. $$ When $\delta = 3i$, inequalities (3) and (4) both give tight bounds, yielding $$|R_i| = 2i + 1.$$ At this limit, the interior arc requirement exactly meets the capacity of $R_i$. If $i > \frac{\delta} {3}$, then inequality (5) fails.

In this case, the required number of interior arcs exceeds what $R_i$ can support, forcing additional exterior arcs to be redirected inward. By the Law of Conservation of Neighbors \ref{connei}, this redirection produces additional transitive triangles, causing the Seymour vertex of some ancestor nodes and contradicting DNSP. Therefore, the rooted neighborhoods cannot extend beyond $R_{\lfloor \frac{\delta} {3} \rfloor + 1}$.
label: Last Rooted Neighborhood

content:

\caption{Decreasing Neighborhood Sequence Algorithm}
• algorithmic
• \State Determine a minimum out-degree node \(v_0 \in V\).
• \State Partition the set of vertices \(V\) into ordered sets \(R_0, R_1, \ldots, R_k\) based on their out-distance from \(v_0\), where \(R_0 = \{v_0\}\) and \(R_i = N^+(R_{i-1}) \setminus \bigcup_{j=0}^{i-1} R_j\) for \(i > 0\).
• \For{\(i = 0\) to \(k\)}
  • \For{each node \(u_i \in R_i\)}
    • \If{there exists an arc \((u_i, w) \in E\) such that \(w \in R_k\) where \(k < i\)}
      • \State \(u_i \rightarrow \text{degree\_doub[back]}\)
      • \State HALT
    • \Else
      • \If{\(i > 0\)}
        • \If{\(|\text{int}(u_{i-1}, u_i)| < i\)}
        • \State \(u_{i-1} \rightarrow \text{degree\_doub[dense]}\)
        • \State HALT
        \EndIf
      \EndIf
    \EndIf
  \EndFor
• \If{\(|R_i| \leq 2\)}
  • \If{\(i > 0\)}
    • \State \(u_{i-1} \rightarrow \text{degree\_doub[size]}\)
    • \State HALT
    \EndIf
  \EndIf

\EndFor
proof:
label: Algorithm for Finding Seymour Vertices

content: Let $G \in \mathcal{O}$ be an oriented graph with minimum out-degree $\delta$. Then there exists a rooted neighborhood $R_i$ that reaches maximal density.
proof: Corollary \ref{ilb} (Iterative Load-Balance) states as nodes move further from the MDN $v_0$, nodes in consecutive rooted neighborhoods take on more load. This means their interior out-degrees increase to prevent predecessors from violating the DNSP. Corollary \ref{nbhsize} (DNSP Impact on Neighborhood Size) shows that the size of rooted neighborhoods decreases as the distance from $v_0$ increases. This combination of shrinking neighborhood sizes and increasing interior degree requirements implies that the density in each neighborhood grows outward from $v_0$. Since the graph is finite, this process cannot continue indefinitely. Each rooted neighborhood $|R_i|$ has more nodes than its successor $R_{i+1}$. Each node in $R_i$ also has a lower degree than in $R_{i+1}$ by Corollary \ref{regint} (Regular Interior Degrees). This means that each successive rooted neighborhood is growing denser. Therefore, there must exist a neighborhood $R_i$ where the density reaches a maximum. Beyond this neighborhood, either DNSP nodes are violated or the neighborhood sizes are too small to accommodate further increases in interior degree. Hence, a last, most densely rooted neighborhood exists.
label: Occurrence of Last Dense Rooted Neighborhood

content: Let $G \in \mathcal{O}$ be an oriented graph with minimum out-degree $\delta$, and let $R_i$ be the last, most dense rooted neighborhood, as noted in Corollary \ref{corr2} (Occurrence of Last Dense Rooted Neighborhood). Then every node in $R_i$ is a Seymour vertex.
proof: From Corollary \ref{corr2}, $R_i$ is the last rooted neighborhood where density reaches a maximum due to shrinking size and increasing interior degrees. By Theorem \ref{regint} (Regular Interior Degrees), each node in $R_i$ must have an interior degree of $i$. Since $R_i$ is the last neighborhood with enough nodes, additional interior degrees cannot be met without exceeding the node count. The neighborhood is saturated, and each node's second out-neighborhood size is at least the first. Theorem \ref{nbhquot} (Rooted Neighborhood Quotient) all nodes must have interior degree $i$ in $R_i$. Otherwise, all parents in $R_{i-1}$ become Seymour vertices. Similarly, because $R_i$ is maximally dense, all nodes in $R_i$ themselves meet the Seymour vertex condition:$$|N^{++}(u)| \ge |N^+(u)|, \quad \forall u \in R_i.$$ Hence, all nodes in $R_i$ are Seymour vertices.
label: Multiple Seymour Vertices

content: Let $G$ be an oriented graph. DNSP algorithm runs in $$O(|V| + |E|),$$ where $|V|$ is the number of vertices and $|E|$ is the number of edges in $G$.
proof: The algorithm proceeds in two main phases:

\textbf{1. Constructing the rooted neighborhood partitions $R_0, R_1, \dots, R_k$.}

Finding a node $v_0 \in G$ of minimum out-degree requires scanning all vertices and their out-degrees. This takes $O(|V|)$ time if out-degrees are stored or computed efficiently.

Partitioning vertices into rooted neighborhoods based on distance from $v_0$ can be done using a BFS. Each vertex is visited exactly once, and each edge is traversed at most once to determine adjacency and assign layers. Hence, constructing the partitions takes $O(|V| + |E|)$ time.

\textbf{2. Running DNSP checks.}

By Corollary \ref{ilb} (Iterative Load-Balancing), every vertex $u_i$ in every neighborhood $R_i$ belongs to at least $i$ disjoint cycles, making them Seymour vertices for those rooted neighborhoods. This property allows the algorithm to identify Seymour vertices without exhaustively checking every possible combination of vertices and edges in each neighborhood.

Since each vertex belongs to exactly one rooted neighborhood, the total number of neighborhoods $k$ is at most $|V|$. Processing each neighborhood involves examining the outgoing arcs of its vertices, which collectively accounts for all edges in $E$. Therefore, this phase also takes $O(|V| + |E|)$ time.

\textbf{Combining both phases:} $$O(|V|) + O(|V| + |E|) + O(|V| + |E|) = O(|V| + |E|).$$ Thus, the overall complexity of DNSP nodes algorithm is linear in the size of the graph, i.e., $O(|V| + |E|)$.
label: Algorithm Complexity

content: Example to show how Partitions and influencer nodes can help with network A/B testing.
proof:
label: GLOVER data structure in network A/B testing

content: Any dataset that can be represented in a structured encoding format (such as JSON, XML, YAML, or equivalent) can be represented using a GLOVER data structure, provided the user selects a valid metric. This will yield a valid GLOVER structure.
proof: Structured encoding formats, including JSON, XML, and YAML, encode data as discrete objects with finite fields and elements. Consequently, the number of elements in any dataset represented by these formats is finite, ensuring the data can be fully enumerated and partitioned. Let \(M\) be the metric chosen by the user such as degree or distance in the Seymour Second Neighborhood Conjecture. \(M\) is a field, attribute, or key present in the encoded data. \(M\) corresponds to the basis for defining relationships across the neighborhoods. For each element \(x\) in the dataset, the metric \(M(x)\) determines a value or set of values that can be used to group elements. The dataset is partitioned into neighborhoods \(R_1, R_2, ..., R_k\) based on \(M\), where \(R_i = \{x \mid M(x) = v_i\}\) for some value \(v_i\). If \(M\) improperly defines neighborhoods (e.g., allows elements to belong to multiple neighborhoods or leaves elements unassigned), then \(M\) is not a valid metric. A valid \(M\) ensures that all elements are correctly assigned to exactly one neighborhood. Thus, any dataset encoded in a structured format can be represented by a Graph Level Order data structure, provided a suitable metric \(M\) exists.
label:

content: Suppose we have an oriented graph \( G \), with minimum out-degree node \( v_0 \). Then, every node \( x \) in the neighboring rooted neighborhood \( R_1 \) must have an interior degree of at least 1. That is, for \( x \in R_1 \), \[ |\text{int}(v_0, x)| \geq 1. \]
proof: By definition, a node satisfies the Decreasing Neighborhood Sequence Property if \[ |N^+(x)| > |N^{++}(x)|. \] By the definition of an interior arc, \[ \text{int}(v_0, x) = N^+(v_0) \cap N^+(x) \] A node \(x \in R_1\), will have exterior out-neighbors in \(R_2\), making them second out-neighbors of \(v_0\). If \(x\) has zero interior arcs, then \(x\) must have \(\delta = d^+(v_0)\) exterior arcs. This means that the size of \(v_0\)'s second neighborhood, \(|N^{++}(v_0)|\) would be at least \(|N^+(v_0)|\), violating the DNSP condition for \(v_0\). This implies that \(x\) must have at least one interior arc to another node in \(R_1\). By definition, \(v_0\) has \(d^+(v_0)\) first out-neighbors. This means that \[ N^{++}(v_0) \geq N^+(v_0). \] To avoid this doubling of \(v_0\), \(x\) must connect to at least one interior arc. This means that the interior degree of \(x\) with respect to \(v_0\) must satisfy \[ |\text{int}(v_0, x)| \geq 1 \] This is true for the out-neighbors of every node in \(R_1\). This ensures that every node in \(R_1\) has an interior degree of at least one. Hence, every node \(x \in R_1\) satisfies \[|\text{int}(v_0,x)| \geq 1.\] Thus, for all \(x \in R_1\), \[ |\text{int}(v_0, x)| \geq 1. \]
label: Interior Load Balancing Lemma

content: Suppose we have an oriented graph \(G\). If \( x \) in rooted neighborhood \( R_i\) has the Decreasing Neighborhood Sequence Property, then for all \(y \in N^+(x), |\text{ext}(x, y)| < d^+(x)\). That is, for any out-neighbor \(y\) of \(x\), the number of exterior out-neighbors of \(x\) which are reached through \(y\) must be less than the out-degree of \(x\).
proof: Assume, for the sake of contradiction, that there is a node \( y \in N^+(x) \) such that \( |\text{ext}(x, y)| \geq d^+(x) \). By definition, \( \text{ext}(x, y) = N^{++}(x) \cap N^+(y)\). Thus, \[ |\text{ext}(x, y)| \subseteq N^{++}(x). \] Then: \[ |N^{++}(x)| \geq |N^+(x)| \geq d^+(x) \] This means that the out-degree of \( x \) at least doubles on the graph \( G^2 \). This contradicts the assumption that \( x \) has the DNSP. This must be true for all \(x\) in \(G\), so we conclude that for all \(y \in N^+(x)\), the number of exterior connections \( |\text{ext}(x, y)| \) must be strictly less than \( d^+(x) \).
label: Exterior Load Balancing Lemma