C
=
Cycle modular sequence of vertices
E
=
Edges set/matrix
F
=
Former main breakpoints set/matrix
u
,
v
=
Vertices in a graph
p
,
q
,
r
,
s
=
Indices in a sequence
(
C
p
,
C
p
−
1
)
=
Current main breakpoint
[
p
,
q
]
∈
C
=
Segment to cut, ranged from
p
to
q
in
C
(
r
,
s
)
∈
C
=
Pair of neighboring vertices representing an edge to insert the segment in between
b
(
E
,
u
,
v
)
∈
{
0
,
1
}
=
{
0
if
(
u
,
v
)
∈
E
1
if
(
u
,
v
)
∉
E
f
(
E
F
,
u
,
v
)
∈
{
0
,
1
}
=
{
0
if
(
u
,
v
)
∈
F
1
if
(
u
,
v
)
∉
F
c
(
C
,
E
,
p
,
q
,
r
,
s
)
∈
{
0
,
1
,
2
,
3
}
=
b
(
E
,
C
p
−
1
,
C
q
+
1
)
+
b
(
E
,
C
q
,
C
s
)
+
b
(
E
,
C
p
,
C
r
)
d
(
C
,
E
,
F
,
p
,
q
,
r
,
s
)
∈
{
0
,
1
,
2
,
3
}
=
f
(
E
,
F
,
C
p
−
1
,
C
q
+
1
)
+
f
(
E
,
F
,
C
q
,
C
s
)
+
f
(
E
,
F
,
C
p
,
C
r
)
b
,
c
,
d
,
f
∈
O
(
1
)
{\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}}}
m
(
C
,
F
,
E
,
p
∈
C
)
∈
{
0
,
1
,
2
,
3
,
∞
}
=
min
q
,
r
,
s
∈
C
(
r
∉
[
p
,
q
]
)
∧
(
s
∉
[
p
,
q
]
)
∧
(
|
s
−
r
|
=
1
)
(
c
(
C
,
E
,
p
,
q
,
r
,
s
)
≠
0
)
→
(
d
(
C
,
E
,
F
,
p
,
q
,
r
,
s
)
≠
0
)
c
(
C
,
E
,
p
,
q
,
r
,
s
)
{\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
m
(
C
,
F
,
E
,
p
)
∈
O
(
|
n
|
2
)
{\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
As we iterate over the different possible values for
q
{\displaystyle q}
, there are incrementally more possibilities for
(
r
,
s
)
{\displaystyle (r,s)}
. Each selection of
(
r
,
s
)
{\displaystyle (r,s)}
implies a possible breakpoint for
(
p
,
r
)
{\displaystyle (p,r)}
.
For each q, for all the valid (r,s) for that q,
T
q
{\displaystyle T_{q}}
will track those that result in no breakpoint for (p,r).
T
q
=
{
C
s
:
s
∉
[
p
,
q
]
∧
∃
r
,
|
r
−
s
|
=
1
,
r
∉
[
p
,
q
]
[
b
(
E
,
C
p
,
C
r
)
=
0
]
}
{\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\}}
U
q
{\displaystyle U_{q}}
will track those s that result in a breakpoint that is a former main breakpoint.
U
q
=
{
C
s
:
s
∉
[
p
,
q
]
∧
∃
r
,
|
r
−
s
|
=
1
,
r
∉
[
p
,
q
]
[
b
(
E
,
C
p
,
C
r
)
=
1
∧
f
(
E
,
F
,
C
p
,
C
r
)
=
1
]
}
{\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\}}
V
q
=
{
C
s
:
s
∉
[
p
,
q
]
∧
∃
r
,
|
r
−
s
|
=
1
,
r
∉
[
p
,
q
]
[
b
(
E
,
C
p
,
C
r
)
=
1
∧
f
(
E
,
F
,
C
p
,
C
r
)
=
0
]
}
D
q
=
{
v
:
(
C
q
,
v
)
∈
E
}
H
q
=
{
v
∈
D
q
:
f
(
E
,
F
,
v
,
C
q
)
=
0
}
{\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\}D_{q}=\left\{v:(C_{q},v)\in E\right\}H_{q}=\left\{v\in D_{q}:f(E,F,v,C_{q})=0\right\}}
W
(
q
)
∈
{
0
,
1
,
2
,
3
,
∞
}
=
{
W
0
(
q
)
if
b
(
E
,
C
p
−
1
,
C
q
+
1
)
=
0
,
W
1
(
q
)
if
b
(
E
,
C
p
−
1
,
C
q
+
1
)
=
1
∧
f
(
E
,
F
,
C
p
−
1
,
C
q
+
1
)
=
0
,
W
2
(
q
)
if
b
(
E
,
C
p
−
1
,
C
q
+
1
)
=
1
∧
f
(
E
,
F
,
C
p
−
1
,
C
q
+
1
)
=
1
W
0
∈
{
0
,
1
,
2
,
∞
}
=
{
0
if
|
T
q
/
D
q
|
≠
0
,
1
else if
(
|
V
q
/
D
q
|
≠
0
∨
|
T
q
∩
H
q
|
≠
0
)
,
2
else if
(
|
U
q
∩
H
q
|
≠
0
∨
|
T
q
∩
D
q
|
)
,
∞
otherwise
{\displaystyle {\begin{array}{lcl}W(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(E,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(E,F,C_{p-1},C_{q+1})=1\end{cases}}\\W_{0}\in \left\{0,1,2,\infty \right\}&=&{\begin{cases}0&{\text{if }}\left|T_{q}/D_{q}\right|\not =0{\text{,}}\\1&{\text{else if }}\left(\left|V_{q}/D_{q}\right|\not =0\vee \left|T_{q}\cap H_{q}\right|\not =0\right){\text{,}}\\2&{\text{else if }}\left(\left|U_{q}\cap H_{q}\right|\not =0\vee \left|T_{q}\cap D_{q}\right|\right){\text{,}}\\\infty &{\text{otherwise}}\end{cases}}\\\end{array}}}