User:Realazthat/Notes/Scrap

Du

${\begin{array}{lcl}C&=&{\text{Cycle modular sequence of vertices}}\\E&=&{\text{Edges set/matrix}}\\F&=&{\text{Former main breakpoints set/matrix}}\\u,v&=&{\text{Vertices in a graph}}\\p,q,r,s&=&{\text{Indices in a sequence}}\\(C_{p},C_{p-1})&=&{\text{Current main breakpoint}}\\\left[p,q\right]\in C&=&{\text{Segment to cut, ranged from }}p{\text{ to }}q{\text{ in }}C\\\left(r,s\right)\in C&=&{\text{Pair of neighboring vertices representing an edge to insert the segment in between}}\\b\left(E,u,v\right)\in \left\{0,1\right\}&=&{\begin{cases}0&{\text{if }}\left(u,v\right)\in E\\1&{\text{if }}\left(u,v\right)\notin E\end{cases}}\\f\left(EF,u,v\right)\in \left\{0,1\right\}&=&{\begin{cases}0&{\text{if }}\left(u,v\right)\in F\\1&{\text{if }}\left(u,v\right)\notin F\end{cases}}\\c\left(C,E,p,q,r,s\right)\in \left\{0,1,2,3\right\}&=&b\left(E,C_{p-1},C_{q+1}\right)+b\left(E,C_{q},C_{s}\right)+b\left(E,C_{p},C_{r}\right)\\d\left(C,E,F,p,q,r,s\right)\in \left\{0,1,2,3\right\}&=&f\left(E,F,C_{p-1},C_{q+1}\right)+f\left(E,F,C_{q},C_{s}\right)+f\left(E,F,C_{p},C_{r}\right)\\b,c,d,f\in O\left(1\right)\\\end{array}}$

${\begin{array}{lcl}m\left(C,F,E,p\in C\right)\in \left\{0,1,2,3,\infty \right\}&=&{\underset {\begin{array}{c}q,r,s\in C\\\left(r\notin [p,q]\right)\wedge \left(s\notin [p,q]\right)\wedge \left(\left|s-r\right|=1\right)\\\left(c\left(C,E,p,q,r,s\right)\neq 0\right)\rightarrow \left(d\left(C,E,F,p,q,r,s\right)\neq 0\right)\end{array}}{\min }}c\left(C,E,p,q,r,s\right)\\\end{array}}$

Naive algorithm

$m\left(C,F,E,p\right)\in O\left(\left|n\right|^{2}\right)$

newedgdes(C,p,q,r,s):
  return { (C[p-1],C[q+1]), (C[q],C[s]), (C[p], C[r]) }

countbps(E,NE):
  newbps = 0
  for ( ne in NE )
    if ( ne !in E )
      ++newbps
  return newbps


countmainbps(F,E,NE):
  newmainbps = 0
  for ( ne in NE )
    if ( ne !in E && ne in F )
      ++newmainbps
  return newmainbps



m(C,F,E,p):
  min = infinity
  n = |C|
  for ( q in range(p,p-2) )
    for ( s in range( q + 2, p ) )
      r = s - 1
      for ( i in range(2) )
        NE = newedges(C,p,q,r,s)
        if ( |NE| != 0 )
          newbps = countbps(F,E,NE)
          newmainbps = countmainbps(F,E,NE)
          
          if ( newbps == 0 || newmainbps > 0 )
            min = newbps < min ? newbps : min
       
        swap(r,s)
  return min

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, $|E|\in O(k|G|)$ instead of $|E|\in O(\left|G\right|^{2})$.

As we iterate over the different possible values for $q$, there are incrementally more possibilities for $(r,s)$. Each selection of $(r,s)$ implies a possible breakpoint for $(p,r)$.

For each q, for all the valid (r,s) for that q, $T_{q}$ will track those that result in no breakpoint for (p,r).

$T_{q}=\left\{C_{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=0\right]\right\}$

$U_{q}$ will track those s, valid with q, that result in a breakpoint (p,r) that is a former breakpoint.

$U_{q}=\left\{C{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=1\wedge f(E,F,C_{p},C_{r})=1\right]\right\}$

$V_{q}$ will track those s, valid with q, that result in a breakpoint (p,r) that are not a former breakpoint.

$V_{q}=\left\{C{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=1\wedge f(E,F,C_{p},C_{r})=0\right]\right\}$

The nice thing about these three sets, is that they can be incrementally calculated. $T_{q}=T_{q+1}\cup \left\{C_{q+1}\right\}$ 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)).

$D_{q}$ is a set that contains the adjacent vertices to $C_{q}$ in G.

$D_{q}=\left\{v:(C_{q},v)\in E\right\}$

All $D_{i}$ can be precalculated in a large table D, for all i in O(|G|^2) time, and be retrieved in O(1).

$H_{q}$ is a set that contains those adjacent vertices to $C_{q}$ in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where $(v,C_{q})\in E\wedge (v,C_{q})\notin F$.

$H_{q}=\left\{v\in D_{q}:f(F,v,C_{q})=0\right\}$

Calculating $H_{q}$ takes a maximum of O(|G|) time, since there can be $|G|^{2}$ edges in E, each $D_{q}$ can have a maximum of O(|G|) adjacent vertices recorded, and $H_{q}$ is linear to $D_{q}$. However, for k-SAT problems, we can assume that each node has a maximum of k adjacent nodes, making $|D_{q}|\in O(k)$, thus making the calculation and size of $H_{q}\in O(k)$.

$m\left(C,F,E,p\right)=\min _{q\in C}W(C,F,E,q)$

$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(F,C_{p-1},C_{q+1})=0{\text{,}}\\W_{2}(q)&{\text{if }}b(E,C_{p-1},C_{q+1})=1\wedge f(F,C_{p-1},C_{q+1})=1\end{cases}}$

$W_{0}\left(C,F,E,q\right)\in \left\{0,1,2,\infty \right\}={\begin{cases}0&{\text{if }}\left|T_{q}\backslash D_{q}\right|\not =0{\text{,}}\\1&{\text{else if }}\left(\left|T_{q}\cap H_{q}\right|\not =0\vee \left|V_{q}\backslash D_{q}\right|\not =0\right){\text{,}}\\2&{\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}}$

$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}}$

$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}}$

Perform an operation

New edges:

$N_{e}(C,p,q,r,s)=\left\{(C_{p},C_{r}),(C_{q},C_{s}),(C_{p-1},C_{q+1})\right\}$

Broken edges:

$B_{e}(C,p,q,r,s)=\left\{(C_{p-1},C_{p}),(C_{q},C_{q+1})(C_{r},C_{s})\right\}$

Next cycle:

$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}}$

$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}}$

$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}}$

$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}}$

$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))$

$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)$

$F^{2}(F_{e},M,C,p,q,r,s)=F\cap M^{2}(M,C,p,q,r,s)$