User:Realazthat/Notes/Scrap

Du

${\displaystyle {\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}}}$

${\displaystyle {\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

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

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

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

${\displaystyle 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\}}$

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

${\displaystyle 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\}}$

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

${\displaystyle 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. ${\displaystyle 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)).

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

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

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

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

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

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

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

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle 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))}$

${\displaystyle 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)}$

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