The Reduction of Directed Cyclic Graph for Task Assignment Problem

theory
2022-08-10

https://www.matec-conferences.org/articles/matecconf/pdf/2018/09/matecconf_mucet2018_06031.pdf

Abstract

タスクにサイクルがあってはいけないので, 有向循環グラフを無向グラフにreductionしたい, パスの向きを逆にすれば良い

1. Introduction

Cordellaらは subgraph isomorphism test を効率的に行う手法を提案した
Tongらはランダムウォークに基づき大規模グラフにおけるbest effort matchingを求めるアルゴリズムを提案した
Tianらは重要なノードをマッチングする段階で最大重みづけ二部グラフマッチングを使用しているが二部グラフが大きいとコスト高い
グラフを簡略化するアプローチとしてグラフを小さな部分に分割する
- 切断辺or頂点を特定すること
Ariffin, SallehはグラフをDAGにKernighan-Linアルゴリズムでreduceすることに力を注いでいる
reductionと二分割の組み合わせで効率的なグラフマッピングの概念を導き出した

2. Problem Statement

{4,5,7,4} はサイクルでどうやって除去する?

目的: サイクルから辺を消去して循環をなくすこと

Feedback Arc Set はグラフから削除するとDAGが残る辺の集合=各サイクルの少なくとも1つのエッジを含む集合
- 類似 Feedback Vertex Set, Minimum Spanning Tree
Minimum Feedback Arc Set: どの辺を削除してもサイズが小さくならない集合
- その中の辺を削除せずに逆にしてもグラフはAcyclic
できるだけ少ない辺を削除して Minimum Feedback Arc Set を得たい: 難しいので近似解が提案されている

3. The Decomposition of Strongly Connected Component

無向グラフ $G = (V, E)$ の各辺に向きを与えると有向グラフ $G$ が得られる
out-degree: 出ていく辺の次数, これが0の時はsinkと呼ぶ(本論文ではtargetと呼ぶ)
強連結成分: $G$ の任意の2ノードで, $i \to j, j \to i$ があるとき

4. Equivalent of the Orientation

各頂点のout-degを変えない向きの変更はSCCが一致する

def. 4.1

$G$ と2つのorientation, $G_{1}, G_{2}$ は各頂点が同じout-degを持っていれば, orientaionが等価という

lem. 4.1

等価な $G$ の orientations $G_{1}, G_{2}$ 有向巡回集合を反転させることによって, 異なるものにする

proof. 4.1

$G_{2}$ で逆方向の辺 $e = (y, z) \in G_{1}$ を選択する.
$deg_{out} (z) = k$ , $G_{2}$ では逆向きになるので, 例えば $g = (z, x)$ というoutが存在する.
それは $G_{2}$ では反対方向を向く必要がある.
よって, $G_{1}$ では $y \to e z \to g x$ となり, $G_{2}$ では逆となる.
新しいノードが挿入されると同じ議論が適用される.
これにより, $G_{1}$ で, $G_{2}$ と反対方向なパスが特定できる.
このパスの向きを逆にするを $G_{2}$ と一致するまで繰り返す.

5. Proposed Technique to the Directed Cyclic Graph

の議論を, fig2 に適用する. $(v_{y}, v_{z}, v_{x})$ を $(v_{4}, v_{5}, v_{7})$ とする.

巡回消去アルゴリズム

1. 各ノードの重みを決定する
2. タスクグラフは辺 (y, z) (y < z) を含む
3. もっとも入力コストが低いノードを親にする
4. 2つの異なるエッジを持ち、同じ子を共有するノードを分解する
5. ステップ4で分解した2つのノードを再結合し、エッジの向きを変更する
6. サイクルが無くなるまで上記を繰り返す

step3
サイクル {4,5,7,4} について
- node 4: { 3: 3 }
- node 5: { 1: 5, 2: 3, 4: 5, 6: 5}
- node 7: { 5: * }
  よってコスト最小のnode 4を親にする
step4: 4 -> 5 -> 7 -> 4 を 4 -> 5 -> 7 と 5 -> 7 -> 4 に分解
step5: same child nodeであるnode 5の辺の方向は変わらない, 7 -> 4 を 4 -> 7 にする

6. Formation of Directed Acyclic Graph

todo サイクル見つける具体的なアルゴリズム知りたい

過ぎるだけの時間じゃ悔しい

Explorer

The Reduction of Directed Cyclic Graph for Task Assignment Problem

The Reduction of Directed Cyclic Graph for Task Assignment Problem

Abstract

1. Introduction

2. Problem Statement

3. The Decomposition of Strongly Connected Component

4. Equivalent of the Orientation

def. 4.1

lem. 4.1

proof. 4.1

5. Proposed Technique to the Directed Cyclic Graph

6. Formation of Directed Acyclic Graph

Graph View

Table of Contents

Backlinks