User:Realazthat/Notes/Scrap: Difference between revisions
Content deleted Content added
| (26 intermediate revisions by the same user not shown) | |||
Line 109:
== Better algorithm ==
If we know something about the size of E, we can improve the complexity. For example, in SAT when converted to DHC, all of the variable graph nodes will have a maximum of 3 edges leading in, and 3 out: Each node is connected to the node to the left, and to the right, and possibly to a clause node. The only nodes that have more than this are the clause nodes themselves, which will have m incoming edges, and m outgoing edges, where m is the number of variables in that clause. Thus, it is bounded by the number of variables in the problem. For 3SAT, it is additionally bounded by three, and for k-SAT, by k. Converting from DHC to UHC splits the incoming edges to one node and outgoing to another. Thus, for a k-SAT problem, <math>|E| \in O(k|G|)</math> instead of <math>|E| \in O(\left|G\right|^{2})</math>.
As we iterate over the different possible values for <math>q</math>, there are incrementally more possibilities for <math>(r,s)</math>. Each selection of <math>(r,s)</math> implies a possible breakpoint for <math>(p,r)</math>.
Line 123 ⟶ 125:
</math>
<math>U_{q}</math> will track those s, valid with q, that result in a breakpoint (p,r) that is a former
<math>
Line 134 ⟶ 136:
\right\}
</math>
<math>V_{q}</math> will track those s, valid with q, that result in a breakpoint (p,r) that are '''not''' a former breakpoint.
<math>
Line 143 ⟶ 148:
\right]
\right\}
</math>
The nice thing about these three sets, is that they can be incrementally calculated. <math>T_{q} = T_{q+1} \cup \left\{C_{q+1}\right\}</math> and so on for U and V. Basically, iterate through each possible q (O(|G|), and for each q, determine which sets the two new possibilities (r,s) go into (O(1) time), and insert them (O(log |G|) time, or O(1) if hashset or similar structure; we will assume O(1)).
<math>D_{q}</math> is a set that contains the adjacent vertices to <math>C_{q}</math> in G.
<math>
D_{q}
=
\left\{ v : (C_{q},v) \in E
\right\}
</math>
All <math>D_{i}</math> can be precalculated in a large table D, for all i in O(|G|^2) time, and be retrieved in O(1).
<math>H_{q}</math> is a set that contains those adjacent vertices to <math>C_{q}</math> in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where <math>(v,C_{q}) \in E \wedge (v,C_{q}) \notin F</math>.
<math>
H_{q}
=
\left\{ v \in D_{q} : f(
\right\}
</math>
Calculating <math>H_{q}</math> takes a maximum of O(|G|) time, since there can be <math>|G|^2</math> edges in E, each <math>D_{q}</math> can have a maximum of O(|G|) adjacent vertices recorded, and <math>H_{q}</math> is linear to <math>D_{q}</math>. However, for k-SAT problems, we can assume that each node has a maximum of k adjacent nodes, making <math>|D_{q}| \in O(k)</math>, thus making the calculation and size of <math>H_{q} \in O(k)</math>.
<math>
m\left(C,F,E,p\right) =
</math>
<math>
W(C,F,E,q) \in \left\{0,1,2,3,\infty\right\}
=
\begin{cases}
W_{0}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 0 \text{,}\\
W_{1}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(
W_{2}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(
\end{cases}
</math>
<math>
W_{0}\left(C,F,E,q\right) \in \left\{0,1,2,\infty\right\}
=
\begin{cases}
0 & \text{if } \left|T_{q}
1 & \
\left(
\left|T_{q} \cap H_{q} \right| \not=0
\
\right) \text{,}\\
2 & \text{else if }
\left(
\left| U_{q} \cap H_{q} \right| \not=
\right) \text{,}\\
\infty & \text{otherwise}
\end{
</math>
<math>
W_{1}\left(C,F,E,q\right) \in \left\{1,2,3,\infty\right\}
=
\begin{cases}
1 & \text{if } \left|T_{q} / D_{q}\right| \not= 0 \text{,}\\
2 & \text{else if }
\left(
\left| T_{q} \cap D_{q} \right| \not=0
\vee
\left| U_{q} \backslash D_{q} \right| \not=0
\vee
\left| V_{q} \backslash D_{q} \right| \not=0
\right) \text{,}\\
3 & \text{else if }
\left(
\left| U_{q} \cap D_{q} \right| \not=0 \vee \left| V_{q} \cap D_{q} \right| \not= 0
\right) \text{,}\\
\infty & \text{otherwise}
\end{cases}
</math>
<math>
W_{2}\left(C,F,E,q\right) \in \left\{2,3,\infty\right\}
=
\begin{cases}
2 & \text{if } \left|T_{q} \cap H_{q}\right| \not= 0 \vee \left( |V_{q} \backslash D_{q}| \not=0 \right) \text{,}\\
3 & \text{else if }
\left(
\left| U_{q} \cap H_{q} \right| \not=0
\vee
\left| V_{q} \cap D_{q} \right| \not=0
\right) \text{,}\\
\infty & \text{otherwise}
\end{cases}
</math>
== Perform an operation ==
New edges:
<math>
N_{e}(C,p,q,r,s) = \left\{ (C_{p},C_{r}), (C_{q},C_{s}), (C_{p-1},C_{q+1}) \right\}
</math>
Broken edges:
<math>
B_{e}(C,p,q,r,s) = \left\{ (C_{p-1}, C_{p}), (C_{q},C_{q+1}) (C_{r}, C_{s}) \right\}
</math>
Next cycle:
<math>
C^{2}\left(C,M,E_{e},p,q,r,s\right) =
\begin{cases}
C^{2_{pq}}(C,p,q,r,s) & \text{if } b(C_{p-1},C_{q+1}) = 1 \wedge f(C_{p-1},C_{q+1}) = 0 \text{,}\\
C^{2_{pr}}(C,p,q,r,s) & \text{else if } b(C_{p},C_{r}) = 1 \wedge f(C_{p},C_{r}) = 0 \text{,}\\
C^{2_{qs}}(C,p,q,r,s) & \text{else if } b(C_{q},C_{s}) = 1 \wedge f(C_{q},C_{s}) = 0 \text{,}\\
C^{2_e}(C,p,q,r,s,m \in M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\
C^{2_e}(C,p,q,r,s,e \in E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\
C & \text{otherwise}
\end{cases}
</math>
<math>
C^{2_{pq}}(C,p,q,r,s) =
\begin{cases}
< [C_{q+1}, C_{r}], [C_{p},C_{q}], [C_{s}, C_{p-1}] > & \text{if } (r < s) \text{,}\\
< [C_{q+1}, C_{s}], [C_{q},C_{p}], [C_{r}, C_{p-1}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
C^{2_{pr}}(C,p,q,r,s) =
\begin{cases}
< [C_{p},C_{q}], [C_{s}, C_{p-1}], [C_{q+1}, C_{r}] > & \text{if } (r < s) \text{,}\\
< [C_{r}, C_{p-1}], [C_{q+1}, C_{s}], [C_{q},C_{p}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
C^{2_{qs}}(C,p,q,r,s) =
\begin{cases}
< [C_{s}, C_{p-1}], [C_{q+1}, C_{r}], [C_{p},C_{q}] > & \text{if } (r < s) \text{,}\\
< [C_{q},C_{p}], [C_{r}, C_{p-1}], [C_{q+1}, C_{s}] > & \text{if } (r > s) \text{,}\\
\end{cases}
</math>
<math>
E_{e}^{2}(E_{e},C,p,q,r,s) =
E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s))
</math>
<math>
M^{2}(M,C,p,q,r,s) =
(M \backslash B_{e}(C,p,q,r,s)) \cap N_{e}(C,p,q,r,s)
</math>
<math>
F^{2}(F_{e}, M,C,p,q,r,s) =
F \cap M^{2}(M,C,p,q,r,s)
</math>
| |||