Kenta Ozeki(National Institute of Informatics, Japan)(JST, ERATO, Kawarabayashi Large Graph Project)

Kempe

Kempeswitchswitch

Kempe equivalentFrom Kempe’s wrong proof of 4 Color Theorem (1879)

Appears in the proof of 4CT (c.f. reducible configurations)

Problem (Mohar `06)

Characterize all cubic bipartite graphs with only one K-equiv. class3-regular graph on the projective plane with 3-edge-colorings

24

31Thm. (Oz.`16+)
NOT K-equiv.

3421

Odd type

Even type: One do NOT induce
4-coloring in the dual

: One does induce
4-coloring in the dualThm.

G : cubic bipartite graph on the projective plane,
G has exactly one Kempe equiv. class

The dual of G

Computing a tree
having a small vertex cover
福永拓郎 (国立情報学研究所)

前原貴憲（静岡大学）との共同研究

背景

背景



背景



監視コスト = 頂点被覆の最小重み

2/3

研究成果

1

頂点被覆コストシュタイナー木問題を導入
監視コストが小さい連結ネットワークを求める最適化問題

2

一般グラフに対する Θ(log n) 近似アルゴリズム

3

ユニットディスクグラフに対する定数近似アルゴリズム

4

平面グラフに対する定数近似アルゴリズム

3/3

Optimal pricing for submodular valuations
with bounded curvature(AAAI 2017, to appear)

Hanna Sumita (NII, ERATO)
joint work with T. Maehara, Y. Kawase, K. Tono, K. Kawarabayashi(Shizuoka Univ.) (Tokyo Tech) (UTokyo)

Items
p(1)

1p(2)

2Buyers
X1X2.
.
.
p(m)

m(NII, ERATO)

12.
.
.

Xnnvaluation for each item set→ a submodular function f
Find: price p & allocation X• maximizes total revenue• (p,X) is stablebuyer’s utility for X 　≧ utility for any item set

Main results: approximation algorithms
Our motivation: submodular func. with small curvatures
ex. budget allocation problem

curvature k = “distance” between f and a linear function
0Approximation ratio of our algorithms

k1← linear

1. Single buyer: 1 – k
2. Multiple buyers:1 – k, violation of stability = 1 – k
3. Multiple collaborating buyers: 1 – k
Algorithms output nearly opt. sol. when curvatures are small

The Constant Inapproximability of the Parameterized
Dominating Set Problem (FOCS 2016)
Yijia Chen (Fudan University),Bingkai Lin (NII)• Our result refutes the existence of constant approximation FPT-algorithms for Min
Dominating Set under the hypothesis W[1]≠FPT.
• An elementary proof bypassing the PCP-theorem.
• Technique contribution:
1. Use Biclique[Lin, SODA 2015] as reduction source.
2. Use graph product operation to boost the gap.
We give a gap-producing fpt-reduction fromk-Clique to Min Dominating Set
1. If G contains a k-clique, then 𝛾𝛾 𝐺𝐺 ′ = 𝑘𝑘𝑘.
2. If G contains no k-clique, then 𝛾𝛾 𝐺𝐺 ′ >GR
Kk𝑐𝑐𝑐𝑐′.

3
3. k’=(𝑐𝑐𝑐𝑐)𝑂𝑂(𝑘𝑘 +𝑐𝑐) .

3
𝑘𝑘 𝑂𝑂(𝑘𝑘 +𝑐𝑐)

4. R runs in time 2G’=R(G,k)

𝛾𝛾 𝐺𝐺𝐺 = k’⊆
GG’=R(G,k)
R|𝐺𝐺|𝑂𝑂(𝑐𝑐) .

 𝛾𝛾 𝐺𝐺 ′ :minimum dominating set size of G’Kk⊈𝛾𝛾 𝐺𝐺𝐺 > ck’Exact Computation of Inﬂuence Spreadby Binary Decision Diagrams (WWW’ 17)
Takanori Maehara1) , Hirofumi Suzuki2) , Masakazu Ishihata2)
1) Shizuoka University, 2) Hokkaido University

Inﬂuence Spread [Kempe–Kleinberg–Tardos’03]• Information propagates over social networks· · · Important topic in viral marketing• Estimate/Maximize the amount of inﬂuence spread
Existing Issue• Computing inﬂuence spread is #P-hardThus all existing studies used Monte–Carlo approximation
1/2

Contributions• The ﬁrst algo. for computing inﬂuence spread exactly• It scales to the real-world networks with m ≈ 100 edges• Application to other inﬂuence-spread related problems
Our Techniques• Enumerate all s-t connected subgraphs by using
binary decision diagrams (BDDs)• New frontier-based search method• BDD’s efﬁcient set family manipulation• Perform bottom-up dynamic programming on the BDDs

2/2

発表者：宮内 敦史（東京工業大学）

Y. Kawase, T. Matsui, & A. Miyauchi:“Additive Approximation Algorithms for Modularity Maximization,”
ISAAC 2016.
入力

無向グラフ G = (V , E)

出力

モジュラリティが最大の分割

発表者：宮内 敦史（東京工業大学）

Y. Kawase, T. Matsui, & A. Miyauchi:“Additive Approximation Algorithms for Modularity Maximization,”
ISAAC 2016.
半正定値計画緩和を用いた加法的近似解法の設計• モジュラリティ最大化問題の 0.4209-加法的近似解法

現在最良の精度保証 0.4672 [Dinh et al. ICDM ’15] を改善
最適値が高いインスタンスに対しては，ほぼ最適な解を出力• 最大モジュラリティカット問題の 0.1660-加法的近似解法

初の非自明な加法的近似解法• 関連する問題への拡張

Dynamic Influence Analysis
in Evolving Networks
大坂 直人 (東京大学) 秋葉 拓哉 (PFN)𠮷田 悠一 (NII & PFI) 河原林 健一 (NII)
Presented at 42nd International Conference on Very Large Data Bases
サンプル

サンプル

影響解析
インフルエンサーは誰？
⇝ グラフアルゴリズム的問題[Kempe-Kleinberg-Tardos. KDD'03]

サンプル

成長するネットワーク
最新の結果を追跡したい！
⇝ 静的手法そのままはNG我々の解法：効率的完全動的索引手法

様々な頂点の影響力

できること
索引構築
解析クエリ
索引更新

理論的性質解析ほぼ線形サイズ
解の精度保証
任意の変更

実験的効率評価
1,000万辺規模に対応
静的手法の10倍高速
1秒未満／変更

Budgeted stream-based active learning
via adaptive submodular maximization
Kaito Fujii, Hisashi Kashima (Kyoto Univ.)

Pool-based Active Learning

Stream-based Active Learning

Instances are
given in advance

Instances arrive
sequentially

Update the model

Update the model

Model

Model

Select an instanceto be labeled

Decide whether
to label or not

OracleAdaptive SubmodularMaximization[Golovin-Krause’10]

OracleA New Framework
Online version[This work]

New framework for stream-based active learning
We solve stream-based active learningas the online adaptive stochastic optimization problem.
1

Design a stochastic objective function fsatisfying policy-adaptive submodularity.

2

Select instances to be labeled based on
constant-factor competitive algorithms for maximizing f .
n /kinstancesn /kinstancesn /kinstancesmax∆(v |ψ0 )max∆(v |ψ1 )max∆(v |ψ2 )···tn: total number ofinstancesk : budget∆: marginal gain

Random-Radius Ball Method for
Estimating Closeness Centrality(to appear in AAAI’17)
稲荷場 渉 (東京大学), 秋葉 拓哉 (PFN), 吉田 悠一 (NII & PFI)
目標: 大規模グラフから中心的な頂点を探したい
距離に基づく中心性𝑪𝜶 𝒗 ≔ ෍ 𝜶 𝒅 𝒖, 𝒗
単調減少関数 𝜶 で重みづけ𝒖≠𝒗.

2頂点 𝒖, 𝒗 の距離► 近くに頂点が多いほど 𝐶𝛼 (𝑣) が大きくなる直観的な定義► 特に 𝛼 𝑥 = 1Τ𝑥 の性質が良いことが知られている[https://en.wikipedia.org/wiki/Network_theory]近似アルゴリズム
ランダムな深さのBFSを全頂点から行う
提案手法のメリット:►►►►

実用的に高速誤差に関する理論保証有り
シンプルで実装が容易
省メモリ

実験結果
実行時間対誤差を比較
誤► 提案手法 (緑, 紫)
差► 既存手法 (水色, 橙)
実行時間