text:
\section{Detection of Fort Neighborhoods} \label{sec:comp}

As defined in Section \ref{sec:structural}, Model 1 can be used to find the power domination number of a general graph $G$. In practicality, this model must be solved by constraint generation and depends on efficient methods for the detection of fort neighborhoods. As is standard in constraint generation strategies, a subset $\mathscr{M}_0 \subset \mathscr{M}(G)$ is generated and a fractional solution to the Linear Program (LP) relaxation of Model 1 is found. Then, a violated constraint in the form of (\ref{cons:1}) is identified and the corresponding fort neighborhood $M$ is added to $\mathscr{M}_0$.

In this section, we discuss the computational complexity of detecting these violated constraints, and provide two computational methods by which violated constraints can be practically identified.

\subsection{Computational Complexity}
The minimum weighted fort neighborhood decision problem, \textsc{Min-M}, is stated as follows: \newline

\noindent
\textbf{Problem}: \textsc{Min-M} \\
\textbf{Instance}: Graph $G$, Function $w:V \to [0,1]$, Integer $k$ \\
\textbf{Question}: Does there exist $M \in \mathscr{M}(G)$ such that $\sum_{v\in M} w(v) < k$? \\

When solving Model 1 with a constraint generation strategy, \textsc{Min-M} is the subproblem that must be solved to find violated constraints. In this context, $k=1$ and the weight function $w$ is the map between vertices in $V$ and their values in a fractional solution to the master problem.

\begin{theorem}
\textsc{Min-M} is in $\mathcal{NP}$.
\end{theorem}
\begin{proof}
  To show \textsc{Min-M} is in $\mathcal{NP}$, consider an arbitrary $\textsc{Min-M}$ instance $\left<G, w, k\right>$ and candidate solution $M \subseteq V$. In linear time it can be determined if $\sum_{v \in M} w(v) < k$ holds. In order to determine if $M \in \mathscr{M}(G)$, we consider the sets $J_M := M \cap J(G)$, $\mathscr{P}_M := \{P \in \mathscr{P}(G) : P \subseteq M\}$, verify that $M = \{J_M\} \cup (\cup_{P \in \mathscr{P}_M} P)$ and that Statements 1 and 2 of Theorem \ref{thm:NS_FN} hold. If $M \neq \{J_M\} \cup (\cup_{P \in \mathscr{P}_M} P)$, then by Lemma \ref{lem:jp-contained} $M \not \in \mathscr{M}$. If either Statement 1 or 2 does not hold then by Theorem \ref{thm:NS_FN}, $M \not \in \mathscr{M}$. In either of these cases $\left< G, w, k\right>$ is determined to be a '$no$' instance. If instead the lemma is satisfied and both statements hold, then $M$ satisfies the conditions of Theorem \ref{thm:NS_FN} and thus $M \in \mathscr{M}$ so $\left<G, w, k \right>$ can be evaluated as a '$yes$' instance.

  The sets $J(G), \mathscr{P}(G), J_M, \mathscr{P}_M$ can all be calculated in linear time, and both Statements 1 and 2 of Theorem \ref{thm:NS_FN} can also be verified in linear time. Thus $\left< G, w, k\right>$ can always be evaluated in a polynomial number of steps.
\end{proof}

We next state a related problem in which a given vertex is required to be in the identified fort neighborhood. We regard this problem as \textsc{Restricted-Min-M}, the restricted minimum weight fort neighborhood problem. \\

\noindent
\textbf{Problem}: \textsc{Restricted-Min-M} \\
\textbf{Instance}: Graph $G$, Vertex $v$, Function $w:V \to [0,1]$, Integer $k$ \\
\textbf{Question}: Does there exist $M \in \mathscr{M}(G)$ such that $\sum_{v\in M} w(v) < k, v \in M$? \\

This second problem is also interesting from a complexity standpoint as it may be possible to create a heuristic for \textsc{Min-M} that finds violated constraints using a local search protocol or by iteratively growing a vertex set. Unfortunately, the following theorem shows that such methods that solve this alternative problem exactly may scale poorly with problem size, due to the complexity of \textsc{Restricted-Min-M}.

\begin{theorem} \label{thm:fort-comp}
\textsc{Restricted-Min-M} is NP-Complete.
\end{theorem}
\begin{figure}
  \centering
  \input{comp_fig}
  \caption{Example of the construction used in Theorem \ref{thm:fort-comp}.}
\label{fig:fort-comp}
\end{figure}
\begin{proof}
  To show \textsc{Restricted-Min-M} is in $\mathcal{NP}$ consider an arbitrary instance, $\left<G, v, w, k \right>$, and a candidate solution $M$. Then $\left<G, v, w, k \right>$ is a '$yes$' instance of \textsc{Restricted-Min-M} if and only if $\left< G, w, k \right>$ is a '$yes$' of \textsc{Min-M} and $v \in M$. Since each of these can be determined in a polynomial number of operations, \textsc{Restricted-Min-M} is in $\mathcal{NP}$.

  To show that \textsc{Restricted-Min-M} is also $\mathcal{NP}$-hard, we provide a polynomial reduction to the well known \textsc{3-SAT} problem. Consider an instance of \textsc{3-SAT}, $\left<f\right>$, where $f$ is a boolean formula in conjunctive normal form, with variables $V_1, \dots, V_k$ and clauses $C_1, \dots, C_\ell$ each consisting of 3 variable assignments. Then let $G' = (V', E')$, where $V' := (\cup_{i=1}^k \{v_i, \bar{v}_i, \hat{v}_i\}) \cup \{c_i\}_{i=1}^\ell \cup \{u_m, u_{\bar{m}}, u_{f_1}, u_{f_2}\}$ and $E' := \{v_ic_j : V_i \in C_j\} \cup \{\bar{v}_i c_j : \bar{V}_i \in C_j\} \cup (\cup^k_{i=1} \{\hat{v}_iv_i, \hat{v}_i \bar{v}_i, \hat{v}_iu_{\bar{m}}, \hat{v}_iu_{f_2}\}) \cup (\cup^\ell_{i=1} \{c_iu_{\bar{m}}, c_iu_{f_2}\}) \cup \{u_{\bar{m}}u_m, u_mu_{f_2}, u_mu_{f_1}\}$. The constructed graph $G'$ contains $\ell+3k+4$ vertices and $5\ell+4k+3$ edges; it can be constructed in a number of steps which is linear with respect to the size of the input $f$. A visualization for this construction is provided as Figure \ref{fig:fort-comp}. In addition, we define a weighting function $w':V(G') \to [0,1]$ such that
  $$ w'(v) =
  \begin{cases}
    \begin{aligned}
    k+1 &\text{ if } v = u_{\bar{m}} \\
    1   &\text{ if } v = v_i \text{ or } v = \bar{v}_i \text{ for some } i \:\: .\\

    0   &\text{ else}
    \end{aligned}
  \end{cases} $$
  We complete the proof by showing that $f$ is satisfiable if and only if $\langle G', u_m, w',$ $k+1 \rangle$ is '$yes$' instance of \textsc{Restricted-Min-M}. First, assume that $f$ is satisfiable, with some variable assignment $\dot{V}_1, \dots \dot{V}_k$ where $\dot{V}_i$ is either equal to $V_i$ or $\bar{V}_i$ for $i \in \{1, \dots, k\}$. Then let $F := \{u_{f_1}, u_{f_2}\} \cup \{v_i : \dot{V}_i = V_i\} \cup \{\bar{v}_i : \dot{V}_i = \bar{V}_i\}$. It is straight forward to show that $F$ is a fort, and has closed neighborhood $M := N[F] = F \cup \{u_m\} \cup \{\hat{v}_i\}_{i=1}^k \cup \{c_i\}_{i=1}^\ell$. Thus $M \in \mathscr{M}(G')$, $u_m \in M$, and $\sum_{v \in M} w'(v) = k < k+1$, so $\left<G', u_m, w', k+1 \right>$ is indeed a '$yes$' instance of \textsc{Restricted-Min-M}.

  Alternatively, assume that $\left< G', u_m, w', k+1 \right>$ is a '$yes$' instance of \textsc{Restr-icted-Min-M}. Then there exists $M \in \mathscr{M}(G)$, $F \in \mathscr{F}(G)$ such that $M = N[F]$, $u_m \in M$, $\sum_{v \in M} w'(v) < k+1$. Since $w'(w_{\bar{m}}) = k+1$, $w_{\bar{m}} \not \in M$ so $u_m \in N(F)$. Since $u_m \in N(F)$, $u_m$ must have at least two neighbors in $F$, thus $u_{f_1}, u_{f_2} \in F$. For each $i$ then, $\hat{v}_i \in N[F]$. Like $u_m$, since each $\hat{v}_i$ is also adjacent to $u_{\bar{m}}$, $\hat{v}_i$ cannot be in $F$ itself and instead must be contained in $N(F)$. Since each vertex in $N(F)$ must have two neighbors in $F$, for each $i$, at least one of $\hat{v}_i$'s two remaining neighbors, namely $v_i$ and $\bar v_i$, must be in $F$. By the pigeonhole principle, if any pair $v_i, \bar v_i$ are both in $F$ then since $M$ is assumed to have total weight less than or equal to $k$, then there exists a pair $v_j, \bar v_j$ such that neither vertex is contained in $F$. This cannot be the case so we see that for any $i \in \{1, \dots, k\}$, either $v_i \in F$ or $\bar v_i \in F$. Using $F$ then, we can construct a variable assignment $\dot V_1, \dots, \dot V_k$ such that for each $i \in \{1, \dots, k\}$, $\dot V_i = V_i$ if $v_i \in F$ or $\dot V_i = \bar V_i$ if $\bar v_i \in F$.

  Next, we consider the set of clause vertices, $c_1, \dots, c_\ell$. As before, since each clause vertex is adjacent to a vertex in $F$ and vertex not in $M$, $\{c_1, \dots, c_\ell\}$ $\subset N(F)$. Since each vertex in $N(F)$ must be adjacent to at least two vertices in $F$, each clause vertex must have at least one adjacent variable assignment vertex in $F$. Since by construction a clause vertex is adjacent to a variable assignment vertex in $G'$ if and only if that variable assignment literal appears in the corresponding clause in $f$, each clause $C_1$ is satisfied by at least one variable assignment literal in $\dot V_1, \dots, \dot V_k$. $f$ is satisfied by variable assignments $\dot V_1, \dots, \dot V_k$, so $f$ is satisfiable.
\end{proof}

\subsection{Computational Methods}
In this section, we provide two approaches for separating violated constraints in Model 1. The first method we present finds fort neighborhoods of minimum weight through the use of an IP. Unfortunately this method scales poorly in larger instances. While few constraints have been incorporated into Model 1 many fort neighborhoods of may have weight 0. Without a tie breaking criterion, large vertex sets may be added to the master problem. When this occurs, a shallow violated constraint is added and little progress is made towards optimality. The second method we present avoids this by identifying minimum cardinality fort neighborhoods with total weight less than 1. We compare the performance of these methods in Figure \ref{tab:sep-results}, noting the improved performance of the cardinality based approach.

We also provide a technique for initializing the constraint set of Model 1. In practice, power grid graphs are often sparse and certain special structures can be identified quickly to generate tight constraints.

\subsubsection{Minimum Weight Fort Neighborhoods}
Utilizing the characterization of fort neighborhoods given by Theorem \ref{thm:NS_FN}, an IP can be used to identify minimum weight fort neighborhoods in general weighted graphs. To simplify notation, given a graph $G$ and weight function $w:V \to [0,1]$, we define $w_v = w(v)$ for all $v \in J(G)$ and $w_P = \sum_{v \in P} w(v)$ for all $P \in \mathscr{P}(G)$. \newline

\noindent \text{\textbf{Model 2: Min Weight Fort Neighborhood}}
{\small
  \begin{align}
    \nonumber\min \:&\sum_{v \in J(G)} w_v M_v  + \sum_{P \in \mathscr{P}(G)} w_P F_P \\
    \text{s.t. }  \:&\sum_{v \in J(G)} M_v + {\sum_{P \in \mathscr{P}(G)} F_P \geq 1} \label{cons:2} \\
        & F_v \leq M_u  & \forall v \in J(G), \forall u \in J(G): v \in N[u]           \label{cons:3} \\
        & F_v \leq F_P  & \forall v \in J(G), \forall P \in \mathscr{P}(G): v \in N(P) \label{cons:4} \\
				& F_P \leq M_v  & \forall P \in \mathscr{P}(G), \forall v \in N(P)                \label{cons:5} \\
        & 2(M_v - F_v) \leq \sum_{\substack{u \in J(G): \\ v \in N(u)}} F_u + \sum_{P \in \mathscr{P}(G)} |N(v) \cap P| \: F_P  & \forall v \in J(G) \label{cons:6} \\
    \nonumber & F_P, F_v, M_v \in \{0,1\} & \forall v \in J(G), \forall P \in \mathscr{P}(G)
\end{align}}

We formally prove the correctness of Model 2 in Theorem \ref{thm:FN-IP}, but first we provide the intuition behind the model's variables and constraints. As shown by Lemma \ref{lem:jp-contained}, fort neighborhoods can be partitioned into a set of junctions and junction paths. Variables $M_v$ indicate the junctions in a candidate fort neighborhood $M$, and variables $F_v$, $F_P$ indicate the junctions and junction paths in the interior of $M$, which we show is a fort. Since Theorem \ref{thm:NS_FN} requires junction paths contained in fort neighborhoods to be in the interiors of those fort neighborhoods, we do not need to include corresponding $M_P$ variables. The candidate fort neighborhood identified by the model, $M$, is indicated by the $M_v$ and $F_P$ variables. Thus, feasible solutions to Model 2 correspond to members of $\mathscr{M}(G)$, while the model's objective function ensures that optimal solutions are minimum weight members of $\mathscr{M}(G)$.

Constraint (\ref{cons:2}) ensures $M$ is non-empty. Constraint (\ref{cons:3}) ensures junctions indicated to be in the interior of $M$ are also indicated to be in $M$. Along with Constraint (\ref{cons:4}), Constraint (\ref{cons:3}) also ensures that each junction in the interior of $M$ is not adjacent to any junction or junction path not in $M$. Constraint (\ref{cons:5}) ensures that junctions adjacent to any junction path in $M$ are also contained in $M$, and Constraint (\ref{cons:6}) ensures that any junction in $M$, but not the interior of $M$, is adjacent to at least two vertices in the interior of $M$.

\begin{theorem}\label{thm:FN-IP}
For any graph $G$, weight function $w$, and optimal solution of Model 2, $M = \{v \in J(G) : M_v = 1\} \cup \{v \in P : P \in \mathscr{P}(G), F_P = 1\}$ is a minimum weight fort neighborhood in $G$.
\end{theorem}

\begin{proof}
  To verify this theorem it suffices to show that for each feasible solution for Model 2, $M = \{v \in J(G) : M_v = 1\} \cup \{v \in P : P \in \mathscr{P}(G), F_P = 1\} \in \mathscr{M}(G)$, and that for each $M \in \mathscr{M}(G)$, there exists a feasible solution for Model 2 such that vertices in $M$ are indicated by the $M_v$ and $F_P$ variables. Since the objective function of Model 2 is simply the total weight of $M$, a feasible solution is optimal if and only if it corresponds to a minimum weight fort neighborhood in $G$.

  First, let $\{M_v\}_{v \in J(G)}, \{F_v\}_{v \in J(G)}, \{F_P\}_{P \in \mathscr{P}(G)}$ be a feasible solution for Model 2, and define $J_M = \{v \in J(G) : M_v = 1\}$, $\mathscr{P}_M = \{P \in \mathscr{P}(G) : F_P = 1\}$, and $M = J_M \cup (\cup_{P \in \mathscr{P}_M} P)$. We prove that $M \in \mathscr{M}(G)$ by showing that $M, J_M,$ and $\mathscr{P}_M$ satisfy the sufficient conditions laid out in Theorem \ref{thm:NS_FN}. Since Constraint (\ref{cons:2}) is satisfied $J_M$, $\mathscr{P}_M$ cannot both be empty, so $M$ cannot be empty. Additionally, for any $v \in J(G)$ such that $v \in N(P)$, since Constraint (\ref{cons:5}) is satisfied: $M_v \geq F_P = 1$. Thus $v \in J_M$. The first condition of Theorem \ref{thm:NS_FN} is satisfied.

  Next we verify the second condition of Theorem \ref{thm:NS_FN}. Consider the set $J_N = \{v \in J_M : N(v) \not\subseteq M\}$. $J_N \subseteq J_M$, so for any $v \in J_N$, $M_v = 1$ must hold. Since $v \in J_N$, there must also exist a vertex $u \in N(v)$ such that $u \not \in M$. Either $u \in J(G)$ or there exists some $P' \in \mathscr{P}(G)$ such that $u \in P$. If $u \in J(G)$ then since Constraint (\ref{cons:3}) is satisfied and $M_u = 0$, $F_v \leq M_u = 0$. If instead there exists $P' \in \mathscr{P}(G)$ such that $u \in P'$ then since $F_{P'} = 0$ and Constraint (\ref{cons:4}) is satisfied, $F_v \leq F_{P'} = 0$. In all cases, if $v \in J_N$ then $M_v = 1$ and $F_v = 0$ must hold. Using this, we prove an identity for all $v \in J(G)$,
  $$ |(N(v) \backslash J_N) \cap M| = \sum_{\substack{u \in J(G): \\ v \in N(u)}} F_u + \sum_{P \in \mathscr{P}(G)} |N(v) \cap P| \: F_P. $$
  Since $J_M$ and each set in $\mathscr{P}_M$ are disjoint the following holds.
  \begin{equation*}
    \begin{split}
      |(N(v) \backslash J_N) \cap M| =& |(N(v) \backslash J_N) \cap (J_M \cup (\cup_{P \in \mathscr{P}_M} P))| \\
      =& |(N(v) \backslash J_N) \cap J_M| + |(N(v) \backslash J_N) \cap (\cup_{P \in \mathscr{P}_M} P)| \\
      =& |N(v) \cap (J_M \backslash J_N)| + |N(v) \cap (\cup_{P \in \mathscr{P}_M} P)|.
    \end{split}
  \end{equation*}
  Additionally for any $u \in J(G)$ such that $F_u = 1$ holds, since Constraint (\ref{cons:3}) is satisfied and $u \not\in J_N$, $u$ must be in $J_M \backslash J_N$. Thus,
  $$ |N(v) \cap (J_M \backslash J_N)| = \sum_{u \in N(v) \cap J(G)} F_u = \sum_{\substack{u \in J(G): \\ v \in N(u)}} F_u. $$
  Then since each $P \in \mathscr{P}(G)$ is disjoint,
  $$ |N(v) \cap (\cup_{P \in \mathscr{P}_M} P)| = \sum_{P \in \mathscr{P}_M} |N(v) \cap P| = \sum_{P \in \mathscr{P}(G)} |N(v) \cap P| \: F_P. $$
  Returning to our first equation, we see that if $v$ is also assumed to be in $J_N$, then Constraint (\ref{cons:6}) ensures that
  $$ |(N(v) \backslash J_N) \cap M| = \sum_{\substack{u \in J(G): \\ v \in N(u)}} F_u + \sum_{P \in \mathscr{P}(G)} |N(v) \cap P| \: F_P \geq 2(M_v - F_v) = 2. $$
Thus the second condition of Theorem \ref{thm:NS_FN} is also satisfied.

Next we show that for any fort neighborhood $M \in \mathscr{M}(G)$, there exists a corresponding feasible solution for Model 2. Consider any $M \in \mathscr{M}(G)$ and for any $v \in J(G)$, let $M_v = 1$ if $v \in M$ and let $F_v = 1$ if $N[v] \subseteq M$. For all $P \in \mathscr{P}(G)$, let $F_P = 1$ if $P \subseteq M$. Lastly, set any unassigned $M_v, F_v, F_P = 0$. Since $M$ cannot be empty, Constraint (\ref{cons:2}) is satisfied. For Constraints (\ref{cons:3}), (\ref{cons:4}), and (\ref{cons:5}), we note that if the left hand side is equal to 0, then the constraint holds vacuously. It suffices then to consider only the cases which the left hand side is equal to 1. By construction, for any $v \in J(G)$, $F_v = 1$ if and only if $N[v] \subseteq M$. For any $u \in J(G): v \in N[u]$, $u$ must be in $M$ so $M_u = 1$. Thus, Constraint (\ref{cons:3}) must hold. Similarly, for any $w \in N(v)$ such that there exists a junction path $P$ containing $w$, $w$ must be in $M$. By Lemma \ref{lem:jp-contained}, since $P \cap M \neq \emptyset$, $P \subseteq M$. Thus $F_P = 1$, so Constraint (\ref{cons:4}) must also be satisfied. Next, consider any $P \in \mathscr{P}(G)$ such that $F_P = 1$, and $v \in N(P)$. By construction, $P \subseteq M$. By the first condition of Theorem \ref{thm:NS_FN}, $v \in M$ so $M_v = 1$; Constraint (\ref{cons:5}) holds.

Lastly, we consider Constraint (\ref{cons:6}). Let $v \in J(G)$. In the case that $(M_v-F_v) = 0$, then since the right hand side is always non-negative the constraint must hold. Thus, we need only consider the case that $M_v = 1$ and $F_v = 0$. In this case, by the way $M_v, F_v$ were constructed, $v \in M$ and $N(v) \not\subseteq M$. We note that for any $u \in J(G)$, $u \in J_N$ if and only if $M_u - F_u = 1$ (equivalently, $M_u = 1$ and $F_u = 0$). By the second condition of Theorem \ref{thm:NS_FN}, $|(N(v) \backslash J_N) \cap M| \geq 2$. Thus, by the counting identity shown before,
$$ 2 \leq |(N(v) \backslash J_N) \cap M| = \sum_{\substack{u \in J(G): \\ u \in N(v)}} F_u + \sum_{P' \in \mathscr{P}(G)} |N(v) \cap P'| F_{P'}. $$
Constraint (\ref{cons:6}) holds, thus every $M \in \mathscr{M}(G)$ corresponds to a feasible solution for Model 2, with an objective value equal to the total weight of the vertices in $M$.
\end{proof}

\subsubsection{Minimum Cardinality Fort Neighborhoods}
As an alternative to identifying minimum weight fort neighborhoods, we next present Model 3. This model is a modification of Model 2 and identifies a minimum cardinality fort neighborhood with total weight less than 1, when model parameter $\epsilon$ is chosen to be a small positive number. \newline

\noindent \text{\textbf{Model 3: Min Cardinality Fort Neighborhood}}
{\small
  \begin{align}
    \nonumber\min \:&\sum_{v \in J(G)} M_v  + \sum_{P \in \mathscr{P}(G) |P|\:F_P} \\
    \nonumber\text{s.t. }  \:&\sum_{v \in J(G)} M_v + {\sum_{P \in \mathscr{P}(G)} F_P \geq 1}  \\
        & F_v \leq M_u  & \forall v \in J(G), \forall u \in J(G): v \in N[u] \nonumber  \\
        & F_v \leq F_P  & \forall v \in J(G), \forall P \in \mathscr{P}(G): v \in N(P) \nonumber \\
				& F_P \leq M_v  & \forall P \in \mathscr{P}(G), \forall v \in N(P) \nonumber    \\
        & 2(M_v - F_v) \leq \sum_{\substack{u \in J(G): \\ v \in N(u)}} F_u + \sum_{P \in \mathscr{P}(G)} |N(v) \cap P| \: F_P  & \forall v \in J(G) \nonumber \\
        &\sum_{v \in J(G)} w_v M_v  + \sum_{P \in \mathscr{P}(G)} w_P F_P \leq 1-\epsilon \label{cons:7} \\
    \nonumber & F_P, F_v, M_v \in \{0,1\} & \forall v \in J(G), \forall P \in \mathscr{P}(G)
\end{align}}

Since the constraints enforced in Model 3 include all of the constraints given in Model 2, any feasible solution of Model 3 is also a feasible solution for Model 2 and thus by Theorem \ref{thm:FN-IP} corresponds to the vertex set of a fort neighborhood. Constraint (\ref{cons:7}) ensures that this fort neighborhood has total vertex weight less than 1. In a graph with vertex weights given by a fractional solution for our master problem, Model 1, any feasible solution for Model 3 provides a violated constraint for Model 1.

By minimizing the cardinality of the fort neighborhood, the inequality that is introduced to the master problem is more difficult to satisfy, thereby imposing a greater restriction on the set of feasible solutions. In our computational experiments, we found that this approach for separating out violated constraints outperformed the strategy using Model 2 as outlined in the previous section.

\subsubsection{Detecting Fort Neighborhoods of Special Forms} \label{sec:M-init}
In addition to adding constraints to Model 1 through the use of Model 2 and 3, fort neighborhoods of special forms can often be efficiently identified and included in Model 1 as an initial constraint set. While these forms of fort neighborhoods may do not appear in all graphs, they occur frequently in graph representations of power grids and can be exploited to benefit computation practice.
\begin{figure}
	\centering
  \input{init_M}
  \caption{\footnotesize Illustrations of fort neighborhoods of type I, II, and III (from left to right, respectively). In each example, $v,u$ are junction vertices and $P_1, P_2$ are junction paths. Fort neighborhoods of these special forms can be quickly detected and included as an initial constraint set for Model 1.}
    \label{fig:init-M}
\end{figure}

We consider fort neighborhoods of three types which can be easily described for a graph $G$ in terms of $J(G)$ and $\mathscr{P}(G)$. A fort neighborhood is of the first type if its vertices consist of a junction $v$, and two junction paths $P_1$, $P_2$ such that $N(P_1) = N(P_2) = \{v\}$. A fort neighborhood is of the second type if its vertices consist of a junction $v$ and a junction path $P$ such that $N(P) = \{v\}$ and $|N(v) \cap P| = 2$. Lastly, a fort neighborhood is of the third type if its vertices can be partitioned into junctions $v, u$ and junction paths $P_1, P_2$ such that $N(P_1) = N(P_2) = \{v, u\}$. Fort neighborhoods of these three special types are illustrated in Figure \ref{fig:init-M}.

In the computational experiments presented in Section \ref{sec:results}, we calculate $J(G), \mathscr{P}(G)$, and initialize the constraint set of Model 1 in a process similar to graph component identification. First, $J(G)$ is determined by iterating through the vertices of $G$. After $J(G)$ has been found, $\mathscr{P}(G)$ is determined by recording the vertex sets of the components of $H = G[V\backslash J(G)]$. When a junction path $P$ is detected, its neighborhood in $G$ is searched and fort neighborhoods of type II can be identified. If a fort neighborhood of type II is detected, then the corresponding constraint can be added to Model 1. If not, then since $P$ must either be adjacent to 1 or 2 junctions, the junctions $P$ is adjacent to can be recorded in an upper triangular $|J(G)|\times|J(G)|$ adjacency matrix like structure. If two junction paths are each adjacent to only one junction, then a fort neighborhood of type I is identified, and likewise if a pair junctions are adjoined by two distinct junction paths then a fort neighborhood of type III is identified. To prevent the accumulation of overlapping constraints, for any junction only the first fort neighborhood of type I or II is added to the initial constraint set of Model 1 and for any pair of junctions only the first fort neighborhood of type III is added.

We note that there are other structures that appear regularly in graph representations of electrical networks, and that these three special types are in no way exhaustive of easily recognizable fort neighborhoods. Possible directions of future work include the incorporation of additional commonly occurring yet small fort neighborhood structures.

config: arxiv


TITLE: Use Rolle to determine the number of possible solution of $f(x) = \sin x + x + 1$
QUESTION [0 upvotes]: Good morning. I've found an exercise that require to find the number of possible solutions of the equation $f(x) = \sin x +x + 1$ in $[0, 2\pi]$ using Rolle's theorem.
How should I proceed? I know that the theorem ask for the function to be continuous in $[a, b]$, to be differentiable in $(a, b)$ and that $f(a) = f(b)$.
$f(x)$ is continuous and differentiable but $f(0) = 1$ and $f(2\pi) = 1 + 2\pi$. How can I go on from here? Should I assume that, since i cannot use Rolle, I'm sure that there cannot be more than one solution?

REPLY [1 votes]: I'm assuming that you're asking about the zeroes of $f$. We have $\sin(x)+1\geq 0$ for all $x$. If $x>0$, then $f(x)>0$ so there are no positive zeroes. It remains to check that $f(0)=1\ne 0$.


TITLE: Strong Induction - Understanding the lateral conditions.
QUESTION [3 upvotes]: I dont want the proof of this statement unless it is necessary for my questions, I just want some clarification.

If cr = 1 would cr-1 = 0?
How is cj 1 or 0? I understand cj is an arbitrarily picked number within the theorem 'line' but why is it limited to a rather boolean value?

REPLY [1 votes]: The theorem is precisely asserting the existence and uniqueness of binary expansions of any positive integer $n$.  That's what the $c_j$'s are: the digits of the binary expansion.
I hope the previous paragraph answers your second question.  As for the first: no, the $c_r$'s can be arbitrary elements of $\{0,1\}$, with the one constraint that the last one of them is $1$ (if they were all $0$ we would get $0$, not a positive integer; and since the expansion is finite there must be a last nonzero term).   So for instance $(c_0,c_1,c_2,c_3,c_4) = (1,1,1,1,1)$ is the binary expansion of $1+2+4+8+16= 31$.


TITLE: Intersection of compact topological space
QUESTION [1 upvotes]: Let $X$ be a compact topological space, and $(Z_n)_{n \geq 1}$ a sequence of closed subsets of $X$, and let $U \subseteq X$ be open such that $\bigcap_{i=1}^\infty Z_i \subseteq U$.
I have to prove that there exists a positive $N$ such that $\bigcap_{i=1}^N Z_i \subseteq U$
How can I prove this? What kind of theorems can I use, maybe the finite intersection property?

REPLY [0 votes]: Suppose that $\bigcap_{i =1}^\infty Z_i \subseteq U$.
The $Z_i$ are closed so $Z_i^\complement$ is open in $X$ and we note that
$$\{U\} \cup \{Z_i^\complement: i =1,2\ldots \}$$ is an open cover of $X$: if $x \notin Z_i^\complement$ for all $i$, so not covered by any of the right hand sets, it's in all $Z_i$ and so in $U$, and so all $x \in X$ are in one of these sets.
Apply compactness of $X$ to get a finite subcover and let $N$ be the largest index of the $Z_i^\complement$ we use in the finite subcover.
Then an $x \in X$ that would be in $\bigcap_{i=1}^N Z_i$ but not in $U$ would not be covered by any set in that finite subcover, so such $x$ cannot exist and the desired inclusion must hold.


TITLE: Bekenstein bound for electron?
QUESTION [4 upvotes]: Using the Wikipedia version of the Bekenstein bound, and substituting the Wikipedia values for electron mass and radius, one obtains 0.0662 bits. Does this really mean that a system, any system, placed inside a sphere the size of an electron, and weighing no more than an electron does, is almost determinate? How about an electron itself? Wouldn't one need at least a few bits to characterise the behavior of an electron in magnetic space?
(I am a professional mathematician but I know very little about physics, I'm sure I'm missing something obvious here...)

REPLY [2 votes]: You have found an elaborate way of calculating $2\pi \alpha/ \ln 2 \approx 0.0661658$. Here, $\alpha \approx 1/137$ represents the fine-structure constant.
The points to note is that:
A) Bekenstein's bound defines the maximum number of nats of information that can be contained in a spherical region as the circumference of that region divided by the reduced Compton wavelength associated with the total energy contained within that region,
and
B) the classical electron radius is equal to the fine structure constant times the reduced Compton wavelength of the electron.
Would you redo your calculation using the electron mass and the reduced Compton wavelength of the electron, you would obtain a value of $9.0647$ bits. However, you would obtain exactly the same value for a proton or whatever other elementary or composite particle you might chose. I would not attach any physical significance to these results.

Added: We currently don't have a consistent quantum gravity theory, and we don't even have an idea what would be the fundamental degrees of freedom in such a theory. Therefore any statement in response to questions like "how many bits/nats of information can be associated with an electron mass" runs the risk of leading to nonsense. Having said this, the holographic (Bekenstein-Hawking / black hole) bound seems more capable of providing reasonable leads. Using $4\pi$ times the square of the reduced Compton wavelength of the electron as area in the BH bound leads to an information content of $S/k = \pi \hbar c /G m^2$ nats. Here $m$ denotes the electron mass. This result for "the information content of a volume large enough to contain an electron" is in essence the square of the ratio of the Planck mass over the electron mass. That's a lot of nats.


TITLE: How can I prove $|a_{m+1}-a_{m+2}+a_{m+3}-...\pm a_{n}| \le |a_{m+1}|$?
QUESTION [1 upvotes]: Give a sequence $(a_n)$ that satisfying:
(i) the sequence is decreasing: $$a_n \ge a_{n+1} \forall n \in \mathbb N$$
(ii) the sequence is converging to $0$: $$(a_n) \rightarrow 0$$
Problem:Prove that $|a_{m+1}-a_{m+2}+a_{m+3}-...\pm a_{n}| \le |a_{m+1}|$ $\forall n \gt m \ge N$ for some $N \in \mathbb N$
I think we shall do this by induction. Let $n=1$, then clearly $|a_{m+1}| \le |a_{m+1}|$. Suppose $n=k$ holds true, then for $n=k+1$,
$|a_{m+1}-a_{m+2}+a_{m+3}-...\pm a_{m+k} \mp a_{m+k+1}|$ ...
For the step $n=k+1$, I give up(the triangle inequality will not work!). So, how do we continue to do this? I have a strange feeling that I have made a big mistake somewhere because this induction is really weird. Please help me proceed with how to prove this strange inequality. I thank you very much.
Note: every term in this sequence MUST BE positive(proven).

REPLY [0 votes]: This is just an induction form of the previous answer:

We will show that $0\le a_{m+1}-a_{m+2}+a_{m+3}-\cdots+(-1)^{k-1}a_{m+k}\le a_{m+1}$
for all integers $k\ge1 \text{ and } m\ge0$ by induction on $k$:
1) This is valid for $k=1$, since $0\le a_{m+1}\le a_{m+1}$.
2) Assume this is valid for all integers $l$ with $1\le l\le k$.
a)  If k is even, then
i) $\displaystyle\sum_{i=1}^{k+1}(-1)^{i-1}a_{m+i}=\sum_{i=1}^{k}(-1)^{i-1}a_{m+i}+a_{m+k+1}\ge0$ and
ii) $\displaystyle\sum_{i=1}^{k+1}(-1)^{i-1}a_{m+i}=a_{m+1}-\sum_{i=1}^{k}(-1)^{i-1}a_{m+i}\le a_{m+1}$  $\;$since $\displaystyle\sum_{i=1}^{k}(-1)^{i-1}a_{m+i}\ge 0$
b)  If k is odd, then
i) $\displaystyle\sum_{i=1}^{k+1}(-1)^{i-1}a_{m+i}=\sum_{i=1}^{k-1}(-1)^{i-1}a_{m+i}+(a_{m+k}-a_{m+k+1})\ge0$ and
ii) $\displaystyle\sum_{i=1}^{k+1}(-1)^{i-1}a_{m+i}=\sum_{i=1}^{k}(-1)^{i-1}a_{m+i}-a_{m+k+1}\le \sum_{i=1}^{k}(-1)^{i-1}a_{m+i}\le a_{m+1}$


TITLE: Probability of selecting 1 of n-i elements in a set of size n when choosing k elements
QUESTION [0 upvotes]: Given a set of $n$ elements, I will choose uniformly at random $k$ distinct elements.
First: Given a set $S$ of $i$ distinct elements from $n$, what is the probability that at least one of the $k$ elements will not be in $S$?

REPLY [2 votes]: $1-$the probability that all of them are in $S$ so $1-\frac{\left({i\atop k}\right)}{\left({n\atop k}\right)}$. Here
$\left({i\atop k}\right)=0$ if $i<k$.


TITLE: Markov Chain Initial Distribution
QUESTION [6 upvotes]: Suppose $\{X_0,X_1,X_2,\dots\}$ is a discrete-time Markov chain taking values in a finite set $\{1,\dots,N\}$ with initial distribution $p_i(0) = P(X_0 = i)$ for $i\in\{1,\dots,N\}$ and transition probability matrix P where the $ij$-th entry $p_{ij} = P(X_k = j \mid X_{k-1} = i)$ for $k\geq 1$ and $i,j\in\{1,\dots,N\}$.
In order for the Markov chain to be well-defined, must we have that $P(X_0 = i)>0$ for all $i\in\{1,\dots,N\}$? If this were not true, then some elements of matrix $P$ would be undefined since the following definition is only valid for $P(X_0 = i)>0$.
$$ p_{ij}=P(X_1 = j \mid X_0 = i) = \frac{ P(X_1 = j, X_0 = i) }{ P(X_0 = i) } $$
In some books dealing with discrete-time Markov chains, I have seen the author set the initial distribution to something like $p_i(0) = 1$ if $i=1$ and $p_i(0)=0$ if $i\neq 1$ to signify that the initial condition is known. Doesn't this cause the transition probability matrix $P$ to be invalid and the underlying probability space ill-defined?

REPLY [0 votes]: Find an arbitrary positive sequence $a_n$ such that $\sum a_n = 1$. Enforce $P(X_0 = i) = a_i$. You can now talk about conditional probability legitimately.


TITLE: Covariance depending on wether the random variables are equally distributed
QUESTION [0 upvotes]: X and Y are two random variables that have the same distribution and they are not independent. True or false,
Cov(X+Y,X-Y)=0
So I used the properties of Covariance and ended up with Var(X)-Var(Y)...Im not sure if this is equal to 0. If they tell you that the random variables are equally distributed, does this mean that they have the same parameters or that they simply follow a certain type of distribution (say Normal, Poisson, etc).
Thanks in advance.

REPLY [1 votes]: "$X$ and $Y$ have the same distribution" means literally that. For example, if $X$ is Poisson with mean $4$, then $Y$ is also Poisson with mean $4$. If $X$ is uniform over the values $\{1,4, 7\}$, then $Y$ is also uniform over those values. And so on.
In particular, $X$ and $Y$ have the same expectation, the same variance,...


TITLE: Is a Feynman diagram depicting a vacuum bubble "that gets real" valid?
QUESTION [3 upvotes]: In exercise I.7.3 of A. Zee's QFT in a Nutshell, we have to draw all the Feynman diagrams of the scalar theory
$$
Z(J) = \int D\varphi e^{i\int d^4x\{\frac 12[(\partial\varphi)^2-m^2\varphi^2]-(\lambda/4!)\varphi^4+J\varphi\}}
$$

describing two mesons producing four mesons up to and including order $\lambda^2$.

I came up with ten different diagrams a)-j) so far:

I think that only diagrams a)-g) are correct, since in h)-j) there seems to be a violation of conservation of energy: There are vacuum bubbles that "come to life"; particles are created "out of nothing".
However, I cannot find any rules in the book that tell me that these three diagrams are invalid.

Am I correct that only a)-g) are correct Feynman diagrams for the problem at hand?
What exact rules are there that tell me which Feynman diagrams are valid and which are not?

REPLY [2 votes]: As explained by @ACuriousMind, even the diagrams with vacuum bubbles that "come to life" are correct Feynman diagrams. However, when one translates the diagrams to actual amplitude terms, these terms don't contribute anything because of the delta function one adds at each vertex for energy-momentum conservation.
The combined energy-momentum of the virtual particles coming from the loop is zero, so there is no way a particle pair with real momentum is coming from that interaction.


TITLE: Expectation value of total energy for the quantum harmonic oscillator
QUESTION [0 upvotes]: A particles unnormalized wavefunction is given as
$$\psi(x)=2\psi_1+\psi_2+2\psi_3.$$
How can I find $\langle E\rangle $ without calculating        $\langle T\rangle$ or $\langle V\rangle     $ first? I'm pretty sure I have $\langle T\rangle      $ and $\langle    V  \rangle$ though, so is the only way to find $\langle E\rangle          $ is to add these two values together? Any help would be appreciated.

REPLY [3 votes]: If you're specifically asked for the expectation values of $T$ and $V$ then the simplest way of getting $\langle E\rangle$ is simply adding $\langle T\rangle$ and $\langle V\rangle$. If you want a direct calculation, your quickest route is probably using the eigenvalue equation
$$H\psi_n=\hbar\omega(n+\tfrac12)\psi_n$$
and the orthonormality of the $\psi_n$.


TITLE: Binary systems and inverse matrices
QUESTION [2 upvotes]: We had a quiz earlier about binary systems. One problem got me thinking for the whole day.
Let $S$ be a subset of $M_{2}(\mathbb{R})$ consisting of all matrices of the form
 $\Bigg[\begin{matrix}  a & a \\  a & a \\ \end{matrix}\Bigg]$, where $a\neq0$.

Show that $S$ is a commutative binary structure under matrix multiplication.
Does it have an identity element? If yes, find it.
Given $A\in S$, does $A^{-1}$ exist in $S$?

I'm mostly interested in the third item, so I'll skip with the first one.
Define $\ast$ to be matrix multiplication. In algebraic structures, we know that an identity element exists if there exists a unique $e$ such that $a\ast e=a$. Since the identity matrix should be an element of $S$, then it should also be in the form of $\Bigg[\begin{matrix}  e & e \\  e & e \\ \end{matrix}\Bigg]$.
Hence,
$$\Bigg[\begin{matrix}  a & a \\  a & a \\ \end{matrix}\Bigg]\Bigg[\begin{matrix}  e & e \\  e & e \\ \end{matrix}\Bigg]=\Bigg[\begin{matrix}  a & a \\  a & a \\ \end{matrix}\Bigg]$$
So we have $2ae=a$. Therefore, the identity element is $\Bigg[\begin{matrix}  \frac{1}{2} & \frac{1}{2} \\  \frac{1}{2} & \frac{1}{2} \\ \end{matrix}\Bigg]$.
For the case of inverse, we can show that the inverse exists if $a\ast a'=e$. Therefore,
$$\Bigg[\begin{matrix}  a & a \\  a & a \\ \end{matrix}\Bigg]\Bigg[\begin{matrix}  a' & a' \\  a' & a' \\ \end{matrix}\Bigg]=\Bigg[\begin{matrix}  \frac{1}{2} & \frac{1}{2} \\  \frac{1}{2} & \frac{1}{2} \\ \end{matrix}\Bigg]$$
So we have $2aa'=\frac{1}{2}$. Hence, its inverse is $\Bigg[\begin{matrix}  \frac{1}{4a} & \frac{1}{4a} \\  \frac{1}{4a} & \frac{1}{4a} \\ \end{matrix}\Bigg]$.
I'm not sure if this is right or wrong. I'm convinced that this is wrong since we can show that the determinant is equal to zero $(a^{2}-a^{2}=0)$. Also, I don't know if this is relevant, but we've been taught the identity matrix for multiplication is always $\Bigg[\begin{matrix}  1 & 0 \\  0 & 1 \\ \end{matrix}\Bigg]$, but since it's not an element of $S$, I don't really know what to do with it.
Here are some of my questions:

Was it okay for me to assume that $\ast$ is defined to be the matrix multiplication? I think it was wrong, but I also don't know where to go with this problem if it's an arbitrary operation.
What does the determinant say about a matrix? Why can't it be equal to zero for a matrix to have an inverse?
If wrong, what is the correct way of proving or disproving its existence?

Please don't use concepts from linear algebra. Just limit it to basic group theory and basic matrix concepts. Any answer would be much appreciated.

REPLY [0 votes]: "Was it okay for me to assume that ∗ is defined to be the matrix multiplication?"

Yes, because you were told to "how that S is a commutative binary structure under matrix multiplication"

"What does the determinant say about a matrix?" (and related questions)

The identity of a binary operation is an element that doesn't change other elements, so $1\star a=a\star 1=a$ for all $a$.
If you consider the set $M$ of all 2x2 matrices, there's only one matrix $I$ for which $AI=IA=A$ for all $A$.
Now, though, you're looking at $S$. Your matrix $E=\Bigg[\begin{matrix}  \frac{1}{2} & \frac{1}{2} \\  \frac{1}{2} & \frac{1}{2} \\ \end{matrix}\Bigg]$ satisfies $EA=AE=A$ for all $A\in S$, so it's an identity within $S$. It's clearly not an identity within $M$, since there are plenty of matrices in $M$ that don't have $EA=AE=A$.
So, if you have a ring structure, there's nothing stopping proper subsets of it from having completely different identity elements. In fact, any time you have an element A of a ring with $A^2=A$, you can find a set of elements of the ring for which $A$ is an identity.
The identity of $M$ is $I$. The identity of $S$ is $E$.
You've worked out inverses in $S$ correctly - every element (except $O$) has an inverse, and you have the right formula for them. Yes, they all have determinant zero, and still have inverses in $S$. They don't have inverses in $M$, but they do in $S$. The determinant is a nice tool for figuring out which matrices have inverses in $M$, but it's no use in $S$, you'll need a different criterion. Maybe $\det_S\Bigg[\begin{matrix}  a & a \\  a & a \\ \end{matrix}\Bigg]=2a$ will do.
Actually, though, you don't need determinants at all for this question. There's a simple rule for testing invertibility in $S$, namely, $a\neq0$, and the traditional determinant $ad-bc$ is not relevant since it's talking about $M$.


TITLE: What kind of function may satisfy this set of properties?
QUESTION [1 upvotes]: What's an explicit, expressible function that I can program on a computer using basic arithmetic that satisfies the following properties:
$$
f \text{ is differentiable}\\
f(0)=0\\
f(1)=1\\
f′(0)=m_1\\
f′(1)=m_2\\
0≤f(x)≤1\ ∀x∈[0,1]\\
f′(x)≥0
$$
I've messed around with some simple polynomial functions of degree 3, 4, 5, and 6 but none of them satisfy the last two properties. I also considered functions of the following forms:
$$
x^a + (1 - x)^b \\
\frac{1}{2^b}(x^a + (1 + x)^b - 1) \\
\frac{1}{2^b}x^a(1+x)^b
$$
None of these provide strong solutions however.
Any ideas?

REPLY [1 votes]: So here's my suggestion in more detail. In order to produce a picture I chose $m_1=2$ and $m_2=4$. Let
$$f(x):=\begin{cases}2x&x\in(-\infty,\frac{1}{4}]\\\frac{1}{2}&x\in[\frac{1}{4},\frac{7}{8}]\\ 4x-3&x\in[\frac{7}{8},\infty)\end{cases}$$
This looks as follows on $[0,1]$:

Of course you will have to choose $f$ depending on $m_1$ and $m_2$: Sometimes a piecewise linear function with 2 pieces is enough. Then choose a symmetric mollifier, that is a function $\varphi\in C^\infty_c(0,1)$ with the property that
$$
\int_0^1\varphi(x) \,\mathrm dx = 1
$$
Then you can check, that the function
$$
g(x):=\frac{1}{\varepsilon}\int_{-\varepsilon}^\varepsilon\varphi\left(\frac{y}{\varepsilon}\right)f(x-y)\,\mathrm dy
$$
leaves $f$ unchanged near $0$ and $1$ provided $\varepsilon$ is small enough, (here smaller than $\frac{1}{4}$) and $g$ is smooth by definition. The plot with the choice $\varepsilon=\frac{1}{6}$ looks as follows:

I hope this helps.