Cut & Count

n-time algorithm for all possible combinations ofsandt, i.e., at mostn² times. We thus obtain the following result:

Theorem 4.4.6. Given a tree decomposition of width at mostω, there exists an algorithm that solves MAXIMUMWEIGHTMINIMALs-tSEPARATORin timeω^O(ω)n³.

consistentifv₁∈V₁andv₂ ∈V₂implies (v₁, v₂)∈/E.

This means that a cut(V₁, V₂)ofV⁰ is consistent if there are no edges betweenV₁ andV₂. We fix an arbitrary vertexvinV1. Then, ifG[V]is connected, then there only exists one consistent cut, namely(V₁, V₂) = (V,∅). Therefore, the number of consistent cuts is odd. Otherwise, ifV does not induce a connected subgraph, the number of consistent cuts is a multiple of two. Therefore, we just need to compute the number of consistent cuts modulo 2 and return yes if the number of consistent cuts is odd, and return no otherwise. the isolation lemma allows us to guarantee (with high probability) that there exists a unique solution (and thus, that we indeed end up with an odd number of consistent cuts).

LetS ⊆2^U be a set of solutions. According to [19, 20], the Cut & Count technique is divided into two parts as follows.

• The Cut part: Relax the connectivity requirement by considering the setR ⊇ Sof possibly connected or disconnected candidate solutions. Moreover, consider the setCof pairs(X;C) whereX∈ RandCis a consistent cut ofX.

• The Count part: Isolate a single solution by sampling weights of all elements inU by the isolation lemma. Then, compute|C|modulo 2 using a sub-procedure. Disconnected candidate solutionsX∈ R \Scancel since they are consistent with an even number of cuts. If the only connected candidatex∈ S exists, we obtain the odd number of cuts.

Given a setUand a tree decompositionhX, Ti, the general scheme of Cut & Count is as follows:

Step 1. Set the integer weight for every vertex uniformly and independently at random by w⁰ :U → {1, . . . ,2|U|}.

Step 2. For each integer weight 0 ≤ W⁰ ≤ 2|U|², compute the number of relaxed solutions of weightW⁰ with consistent cuts modulo 2 on a tree decomposition. Then return yes if it is odd, otherwise no in the root node.

We use the Cut & Count technique to determine whether there exists a connected partition (S, A, B, Q)of weightW so thatAandB are connected. To apply the above scheme, we newly give the following definition of apartial solution. Note that we have to consider two consistent cuts ofAandB.

Definition 4.5.4. Given a nodeiof the tree decomposition ofG, apartial solutionfor that node is a tuple(S∅, SA, SB, SAB, Al, Ar, Bl, Br, Q, w), such that:

• Vi =S∅∪SA∪SA∪SAB∪Al∪Ar∪Bl∪Br∪Q,

• (Al, Ar)is a consistent cut: there exists no edge(u, v)∈Esuch thatu∈Alandv∈Ar,

• (Bl, Br)is a consistent cut: there exists no edge(u, v)∈Esuch thatu∈Blandv∈Br,

• w= Σv∈Sw(v),

• ∀v∈S_∅,N(v)∩(A_l∪A_r∪B_l∪B_r) =∅,

• ∀v∈S_A,N(v)∩(B_l∪B_r) =∅andN(v)∩(A_l∪A_r)6=∅,

• ∀v∈S_B,N(v)∩(B_l∪B_r)6=∅andN(v)∩(A_l∪A_r) =∅and

• ∀v∈S_AB,N(v)∩(B_l∪B_r)6=∅andN(v)∩(A_l∪A_r)6=∅.

• s∈V_i ⇒s∈A_l

• t∈V_i ⇒t∈B_l

For each vertexv, we set another weightw⁰(v)by choosing from{1, . . . ,2|V|}independently at random. We also define the coloring functionc:V → {s_∅, sA, sB, sAB, al, ar, bl, br, q}. Now, we give a dynamic programming algorithm that computes the number of relaxed solutions with consistent cuts modulo 2. To compute that, for eachc,wandw⁰, we define thecountingfunction h_i :{s_∅, s_A, s_B, s_AB, a_l, a_r, b_l, b_r, q}^|Xi|×N×N→Nin each nodeion a nice tree decomposition.

Here, we define the function[p]as follows: ifpis true, then[p] = 1, otherwise[p] = 0.

Leaf node: In a leaf node, we define h_i(∅,0,0) = 1, ifS_∅ = S_A = S_B = S_AB = A_l = Ar =B_l =Br =∅andw, w⁰ = 0. Otherwise,hi(c, w, w⁰) = 0.

Introduce vertexvnode: The functionh_ihas five cases in introduce vertex nodes. Note that we only add one vertexvwithout edges. Thus, ifc(v) ∈ {s_A, sB, sAB}, the partial solution is invalid by definition becausevhas no neighbor. Ifc(v) =s_∅, vertexvis chosen as a vertex ofS, and we hence add each weightw(v),w⁰(v)tow,w⁰, respectively. Moreover,vmust not bes,tbecauses

(resp.,t) should be inA_l(resp.,B_l). If not, it is not a connected partition. Similarly, ifc(v) = a_l (resp.,bl), we check whethervis nott(resp.,s). As forc(v) ∈ {a_r, br, q}, we also check whether vis neithersnort. Therefore, we defineh_iin introduce vertex nodes as follows:

hi(c× {c(v)}, w, w⁰) :=



































[v6=s, t]h_j(c, w−w(v), w⁰−w⁰(v)) ifc(v) =s_∅ [v6=t]h_j(c, w, w⁰) ifc(v) =a_l [v6=s]h_j(c, w, w⁰) ifc(v) =b_l

[v6=s, t]h_j(c, w, w⁰) ifc(v)∈ {a_r, b_r, q}

0 otherwise.

Introduce edge (u, v) node: In introduce edge nodes, we check each state of the endpoints of the edge(u, v)and definef_ifor each case.

• Ifc(u) = s_∅, vertexuhas no neighbor inAandB. Hence, we define the functionh_iin this case as follows:

hi(c× {c(u)} × {c(v)}, w, w⁰) := [c(v)∈ {a/ _l, ar, bl, br}]

·h_j(c× {s_∅} × {c(v)}, w, w⁰).

• If c(u) = s_A, vertex u has neighbors in A but no neighbor in B. In this case, we have two cases. The first case is that u ∈ S∅ and v ∈ A in the child node, because by adding edge (u, v) in the introduce edge (u, v) node, vertex u is moved from S_∅ to S_A. The other case is that u ∈ SA and v /∈ B in the child node. If v ∈ B, vertex u is in S_AB in the parent node. We define h_i as follows. Note that only if c(v) ∈ {a_l, a_r}, we sum up two cases. If c(v) ∈ {b_l, br}, hi(c× {c(u)} × {c(v)}, w, w⁰) := 0, otherwise h_i(c× {c(u)} × {c(v)}, w, w⁰) :=h_j(c× {s_A} × {c(v)}, w, w⁰).

h_i(c× {c(u)} × {c(v)}, w, w⁰) := [c(v)∈ {a_l, a_r}]h_j(c× {s_∅} × {c(v)}, w, w⁰) + [c(v)∈ {b/ _l, b_r}]h_j(c× {s_A} × {c(v)}, w, w⁰).

• The case thatc(u) =s_B is almost the same as in the above case, however, we swap the roles ofAandB.

h_i(c× {c(u)} × {c(v)}, w, w⁰) := [c(v)∈ {b_l, b_r}]h_j(c× {s_∅} × {c(v)}, w, w⁰) + [c(v)∈ {a/ _l, a_r}]h_j(c× {s_B} × {c(v)}, w, w⁰).

• If c(u) = s_AB, we consider three cases: u ∈ S_A and v ∈ B, u ∈ S_B andv ∈ A, and u ∈SAB andvis in an arbitrary set in the child node. For first and second case, vertexuis moved fromS_A(resp.,S_B) intoS_ABby adding edge(u, v). Ifu∈S_AB,vis allowed to be in any set because a vertex inSAB could connect to all sets. Therefore, we definefias follows:

hi(c× {c(u)} × {c(v)}, w, w⁰) := [c(v)∈ {b_l, br}]h_j(c× {s_A} × {c(v)}, w, w⁰) + [c(v)∈ {a_l, ar}]h_j(c× {s_B} × {c(v)}, w, w⁰) + hj(c× {s_AB} × {c(v)}, w, w⁰).

• Ifc(u) ∈ {a_l, a_r}, thenc(v) ∈ {b/ _l, b_r, q}since there is no edge betweenA, BandQby the definition of connected partition. There is also no edge betweenA_landArbecause(A_l, Ar) is a consistent cut. Therefore, ifuis inA_lorA_r, thenvis in the same set asuor is in one of SAandSAB. Note that becauseuis inA,vis not inS_∅,SB.

hi(c× {c(u)} × {c(v)}, w, w⁰) := [c(v) =c(u)]hj(c× {c(u)} × {c(v)}, w, w⁰) + [c(v)∈ {s_A, sAB}]h_j(c× {c(u)} × {c(v)}, w, w⁰).

• The case thatc(u)∈ {b_l, b_r}is almost the same as in the above case, however, we replaceA

byB.

hi(c× {c(u)} × {c(v)}, w, w⁰) := [c(v) =c(u)]hj(c× {c(u)} × {c(v)}, w, w⁰) + [c(v)∈ {s_B, sAB}]h_j(c× {c(u)} × {c(v)}, w, w⁰).

• Ifc(u) =q, vertexuis inQ. Hence,vmust be inS_∅, S_A, S_B, S_AB, orQbecause a vertex in Qhas no neighbor inAandB by the definition of connected partition.

hi(c× {c(u)} × {c(v)}, w, w⁰) := [c(v)∈ {s_∅, sA, sB, sAB, q}]

·h_j(c× {c(u)} × {c(v)}, w, w⁰).

Forget v node: For forget nodes, ifc_j(v) ∈ {s_∅, s_A, s_B}, a partial solution does not satisfy the condition of connected partitions because anyv ∈ S must have neighbors of both AandB. For this reason, we only sum up for each statec_j(v)∈ {s_AB, a_l, a_r, b_l, b_r, q}. The functionh_iin forget nodes is defined as follows:

hi(c, w, w⁰) := X

cj(v)∈{s_AB,a_l,ar,b_l,br,q}

hj(c× {c_j(v)}, w, w⁰).

Join node: We denote the coloring and weight for each partial solution ini, j1, j2 byci, cj1, cj2

andw_i,w_j1, w_j2,w⁰_i, w_j⁰

1, w⁰_j

2, respectively. Moreover, for a state subsetL ⊆ {s_∅, s_A, s_B, s_AB, a_l, ar, b_l, br, q}, we definec⁻¹(L) as the vertex set such that all vertices satisfyc(v) ∈ L. For a coloringc_i, we also define the subsetDof tuples of(c_j1, c_j2)as the combinations of colorings of cj1,cj2 like Section 3 such that:

• ∀v∈c⁻¹_i ({s_∅, a_l, a_r, b_l, b_r, q}),(c_j1(v), c_j2(v)) = (c_i(v), c_i(v)),

• ∀v∈c⁻¹_i ({s_A}),(c_j1(v), c_j2(v)) = (s_A, s_∅),(s_∅, s_A),(s_A, s_A),

• ∀v∈c⁻¹_i ({s_B}),(c_j1(v), c_j2(v)) = (s_B, s_∅),(s_∅, s_B),(s_B, s_B), and

• ∀v∈c⁻¹_i ({s_AB}),(c_j1(v), c_j2(v)) = (s_AB, s_∅),(s_AB, s_A),(s_AB, s_B), (sAB, sAB),(s∅, sAB),(sA, sAB),(sB, sAB),(sA, sB),(sB, sA).

LetS^∗be the vertex subsetc⁻¹_i ({s_∅, s_A, s_B, s_AB}). To sum up all combinations of vertex states and weights for counting, we define the function hi. If D = ∅, we definehi(ci, wi, w_i⁰) := 0.

Otherwise,

hi(ci, wi, w_i⁰) := X

wj1+wj2

=wi+w(S∗)

X

w0 j1+w0

j2

=w0 i+w0(S∗)

X

(c^∗_j

1,c^∗_j

2)∈D

hj1(c^∗_j1, wj1, w⁰_j1)hj2(c^∗_j2, wj2, w⁰_j2).

From now, we analyze the running time of this algorithm. In leaf, introduce vertex, introduce edge, and forget nodes, we can computef_i for each coloringcand weightw, w⁰ inO(1)-time be-cause we only useO(1)-operations. Therefore, the total running time for them isO^∗(9^ω·W ·W⁰).

However, in join nodes, we sum up all weight combinations and coloring combinations satisfying some conditions. There are 21 coloring combinations for each vertex andW ·W⁰ weight combina-tions. Therefore, we compute allf_i’s in a join node in timeO^∗(21^ω·W²). Note that by definition, O(W⁰²)is a polynomial factor.

Theorem 4.5.5. Given a tree decomposition of width at mostω, there exists a Monte-Carlo algo-rithm that solves the decision version of MAXIMUM WEIGHT MINIMAL s-tSEPARATORin time O^∗(21^ω·W²). It cannot give false positives and may give false negatives with probability at most 1/2.

Using the convolution technique [110], we can obtain a faster Monte-Carlo algorithm. The technique helps to speed up the computation for join nodes. First, we set the new coloring ˆ

c:V → {sA¯B¯, sA¯, sB¯, sall, al, ar, bl, br, q}. The statesA¯B¯ represents that a vertexvis inSand has no neighbor ofAandB. The statesA¯ (resp.,sB¯) represents a vertexvis inSand has no neighbor ofA(resp.,B), respectively. Finally, the statesallrepresents a vertexvis inSwithout constraints.

Then, we show the following lemma to transform betweencandˆc.

Lemma 4.5.6. Letibe a node of a tree decomposition andh_i(c, w, w⁰) be a counting function to count the number of partial solutions of MAXIMUM WEIGHT MINIMALs-tSEPARATORof each weightw, w⁰, corresponding to each coloringc,cˆof a nodei. Then we can transform from one coloring to another coloring for each function without loss of information. Moreover, it is computed inO(W ·W⁰·9^ω· |X_i|).

Proof: This proof scheme follows [110]. We consider the immediate`-th step in the transformation.

Forh_i(c× {c(v)} ×c, w, wˆ ⁰),vis a vertex which turns into the state of another coloring in the`-th step, andcis the partial coloring of size`−1andˆcis also the partial coloring of size|X_i| −`. Here, for simplicity, we denoteh_i(c× {c(v)} ׈c, w, w⁰)andh_i(c× {ˆc(v)} ׈c, w, w⁰)byh_i(c(v))and hi(ˆc(v)).

Sinceh_iis the number of partial solutions with a consistent cut, the transformation fromctoˆc ofhiin`-th step is as follows:

- hi(sA¯B¯) =hi(s∅)

- hi(sA¯) =hi(s∅) +hi(sB) - hi(sB¯) =hi(s∅) +hi(sA)

- hi(sall) =hi(s∅) +hi(sA) +hi(sB) +hi(sAB).

Conversely, we can transform fromcˆtocas follows:

- h_i(s_∅) =h_i(sA¯B¯)

- h_i(s_A) =h_i(sB¯)−h_i(sA¯B¯) - h_i(s_B) =h_i(sA¯)−h_i(sA¯B¯)

- h_i(s_AB) =h_i(s_all)−h_i(sA¯)−h_i(sB¯) +h_i(sA¯B¯).

These equations follow from equations of the transformation fromctoc.ˆ

For each of the coloringsc,ˆc, each transformation can be performed inO(|X_i|)-steps. Thus, the total running time of each direction isO(W ·W⁰·9^ω· |X_i|).

Therefore, we first transform the original coloringcto the new coloringcˆinO(W·W⁰·9^ω·|X_i |)-time. Then we compute the following functionh_ifor the new coloringˆcinO(9^ω·W²)-time:

h_i(ˆc, w_,w_i⁰) := X

wj1+wj2=wi+w( ˆS^∗)

X

w⁰_j

1+w⁰_j

2=w_i⁰+w⁰( ˆS^∗)

h_j1(ˆc, w_j1, w⁰_j1)h_j2(ˆc, w_j2, w_j⁰₂),

whereSˆ^∗ = ˆc⁻¹({s_∅, sA, sB, sAB}) ⊆V. Note thatˆci,cˆj1,ˆcj2 are the same coloring. Finally, we transformˆctoc. Thus, total running time of this algorithm isO^∗(9^ω·W²).

s_∅ sA sB sAB al ar bl br q s∅ s∅ sA sB sAB

sA sA sA sAB sAB

sB sB sAB sB sAB

sAB sAB sAB sAB sAB

ar ar

al al

br br

bl bl

q q

Table 4.2. Combinations of the original coloring in join node

sall sA¯ sB¯ sA¯B¯ al ar bl br q sall sall

sA¯ sA¯

sB¯ sB¯

sA¯B¯ sA¯B¯

ar ar

al al

br br

bl bl

q q

Table 4.3. Combinations of the new coloring in join node

Theorem 4.5.7. Given a tree decomposition of width at mostω, there exists a Monte-Carlo algo-rithm that solves the decision version of MAXIMUM WEIGHT MINIMAL SEPARATORand MAXI

-MUM WEIGHT MINIMALs-tSEPARATORin timeO^∗(9^ω·W²). It cannot give false positives and may give false negatives with probability at most1/2. If the input graph is unweighted, the running time is9^ωn^O(1).

As usual for this type of algorithm, the probability of a false negative can be made arbitrarily small by repeating the algorithm.

ドキュメント内 経済構造分析におけるグラフ最適化とネットワーク 指標に関する研究 (ページ 87-95)