Depth

Discrete Math, Graph
TheoryDiscrete Mathematics
Combinatorial Optimization
Probability and Statistics
Numerical Analysis and Linear Algebra
Number theory
Algorithm
Theoretical Computer Science
Bioinformatics
Machine Learning
Data Mining
Natural Language
Data base
SystemEconomics
Social science
Theoretical Physics (Statistical Physics)

Algorithm andTheoretical CS

Big Data

ＪＳＴ ＥＲＡＴＯ Kawarabayashi Large
Graph Project

Scheduling Baseballapplication

STOC, FOCS, SODA: 理論計算機科学のトップ会議
 また暗号(Crypto)，プライバシー(Privacy), 量子計算量でもベストな結果が発表される！
 しかし実際は，，， 「難関」数学！
 誰も実装はしない。実装にはほぼ意味がない。おそらく興味すらない。
→ 理論家の論文をそのまま実装してはだめ 近年のトレンド： 離散数学，解析，確率，整数論, 幾何，代数などから，超「難関」数学の応用と拡張が中心
 数学のビッグネームの参入： Terry Tao, Tim Gowers, Laszlo Lovasz,Lex Schrijver, Noga Alon, Endre Szemeredi, Assaf Naor, Yuval Peres,Jeff Cheeger, Bruce Kelner…（フィルーズ賞，アーベル賞，あるいはアーベル賞候補者）


理論の世界： ＳＴＯＣ，ＦＯＣＳ，ＳＯＤＡ世界
チューリング賞受賞者や，ネバンリンナ賞受賞が，大量にいる世界 ＋ 未来のチューリング賞受賞候補がたくさんいる世界（おそらくチューリング賞を最も輩出している分野）
過去３０年のチューリング賞受賞者
Richard Karp (1985), Hopcroft and Tarjan (1986),
Juris Hartmanis and Richard E. Stearns(1993),
Mauel Blum(1995), Andrew Yao(2000), Rivest, Shamir,Adleman(2002), Leslie Valiant(2010), Micali, Goldwasser(2012)
ネバンリンナ賞
Tarjan(82), Valiant(86), Razborov(90), Wigderson(94), Shor(98)Sudan(02), Kleinberg(06), Spielman(10), Khot(14)ユダヤ人が半数以上！
Ｎｏｎ－ＵＳ, Non-Israel： Mikkel Thorup, Ken-ichi Kawarabayashi
Under 40: Venkastesan Guruswami, Anupam Gupta
Ken-ichi Kawarabayashi

理論研究の世界： ＳＴＯＣ，ＦＯＣＳ，ＳＯＤＡ世界
ここで生き残るのは結構つらい！
→ 理論屋さんだけでやっていくのは結構つらいよ！
→ でも他の分野でも活躍できる！
でも… 数学なのに、評価される理由
１．実用面での貢献をした研究者も多い
２．理論が強い学生は、常に優良物件！
３．他分野にも影響を与える研究者も多い！

Ａｌｏｎ： アーベル賞を10年以内にとりそうな数学者
Ｌｅｉｇｈｔｏｎ： Akamaiの創始者
Ｋｌｅｉｎｂｅｒｇ．．．
Ｐｉｏｔｒ Ｉｎｄｙｋ： ＩＣＭＬ‘１５ ベストペーパー
Ragahavan: Former Y! research director
S. Muthukrishnan: Databaseでもビッグネーム
Motowani： Brin, PageのPDメンター
C. Dvorak： Privacyでの超有名人
その他： 理論研究者が他分野で、論文をたくさん発表！

1. Ken-ichi Kawarabayashi, Mikkel Thorup
Deterministic Global Minimum Cut of a Simple Graph in Near-linear Time
2. Ken-ichi Kawarabayashi and Stephan Kreutzer,
The Directed Grid Theorem
3. Ken-ichi Kawarabayashi and Anastasios(Tasos) Sidiropoulos
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
90/323..

STOC‘１５ Result: Edge Connectivity
Graph Cut： One of the most famous problem
Partition G into (A,B) such that # of edges
between A and B is as small as possible.
G: n vertices and m edges.
K: cut size
Race by many ``giant’’ researchers in theory!
Ford and Fulkerson’56
O(mn2) ←Founder of Operation Research！
Turing prize winnerEven and Tarjan’75
O(nm1.5) ←←Russian researchers
Karzanov and Timofeev’86 O(n3)Hao and Orlin’92
O(nm log(n2/m)) Deterministic
Deterministic
Ibaraki and Nagamochi’92 O(nm+n2log n)
Gabow’93
O(km)Deterministic (for simple graphs)(Randomize, Monte Carlo, Random Contraction)
Karger’94
O(mn0.5)(Randomize, Monte Carlo)
Karger and Stein’96
O(n2 log3 m)(Randomize, Monte Carlo, Tree Packing)Karger’99
O(m log3 n)
Deterministic! (for simple graphs)
KK and Thorup(STOC’15) O(m log１０ n)

Min-Max Theorem(Ford and Fulkerson)
Given s and t,
Max # of edge-disjoint paths (flows)= Min # of edge cut s and tstRace by many ``giant’’ researchers in theory!
Ford and Fulkerson’56
O(mn2) ←Founder of Operation Research！
Even and Tarjan’75
O(nm1.5) ←Turing prize winner
Karzanov and Timofeev’86 O(n3)←Russian researchers
Hao and Orlin’92
O(nm log(n2/m)) Deterministic
Ibaraki and Nagamochi’92 O(nm+n2log n)
Deterministic
Gabow’93
O(km)Deterministic (for simple graphs)
Karger’94
O(mn0.5)(Randomize, Monte Carlo, Random Contraction)
Karger and Stein’96
O(n2 log3 m)(Randomize, Monte Carlo)
Karger’99
O(m log3 n)(Randomize, Monte Carlo, Tree Packing)
KK and Thorup(STOC’15)
O(m log１０ n)
Deterministic! (for simple graphs)

Monte Carlo Algorithm:
Guarantee the time complexity, and with high probability,
the answer is correct.
Kager’s mincut: NO WAY to check that the cut is min…
Las Vegas Algorithm:
Guarantee the correctness, but with small probability,
time complexity takes forever..
Key Observation 1:
Let C be a ``minimum’’ cut (of order at most k). Either
1.
One side is trivial (note that min degree is at least k), or2.
Both sides contain at least k-1 vertices..
Our luck:
Can assume that k > log3 m (otherwise, we can get a min cut algorithm withrunning time O(km) by Gabow, and done.)
In 2, we get a ``sparse’’ cut (i.e., low conductance cut)!
Log n is a ``magic’’ number… → KEY IDEA! Keep applying sparsest cut!

Observation 2:
Q: a subgraph s.t. each vertex in Q has degree at least k/2 in Q. If no sparsest
cut of conductance k/4 in Q → Q is contractible(preserving all min nontrivial cuts)!

Note: k > log3 n. So conductance is small..
The idea:
Find contractible subgraphs Q’ such that after the contraction, the graph has at
most m/k edges (but all nontrivial cuts are there).
→ By Gabow’s, we get an O(m) algorithm.
How to find contractible subgraphs? Repeatedly cutting sparsest cuts!
→ When we stuck, we get ‘’contractible’’ subgraphs!

PageRank! (starting from one vertex) &Sparsest cut!
(Andersson, Chung, Lang)

Key Observation:
Let G be a simple graph with min degree k. If min-cut W is not trivial, then # of cut
edges of W is at most factor 2/k of # of edges in components.
→ we can use PageRankto find a sparsest cut W’(with error factor log n << k)!
→ # of cut edges for W’ isat most factor (2 log n/k) of# of edges in W’ in O(m)!
k > log5m

Big Side G-W

If we can ``correctly’’ guess a vertex v inW and start PageRank from v, we can get asparse cut of conductance o(1/log n).
More we can say….

Min cut

Small side W

Min cut

If u gets ‘’small (< 1/m),
Then we can find a sparse cut!

Small side W
Big Side G-W

Small side W

Min cutSmall side W

Fix PageRank score after the cut of W
→ Gauss-Southwell (KDD’15)!
→ Time complexity: O(|W|)

If we cannot find low-conductance (sparse) cut in W, then W iscontractible.
 The point:
Only apply O(log n) iterations to the small side W → average degree isk – O(log2 n) >> k/2...
Can do each ``small’’ component separately..
→ spend only O(m) in total. Then we can find contractible subgraphs!

In the end, we have a graph with O(m/k) edges.
Well, cheating…..

The Directed Grid TheoremKen-ichi Kawarabayashi, NII, Tokyo
Stephan Kreutzer, TU Berlin（ICALPのほうが詳しい）

Stephan Kreutzer – TU Berlin

Algorithmic Digraph Structure Theory

Undirected Graphs

Directed Graphs

all graph classes…
excluded minors

The Grid Theoremlin. local tree width
planartrees

tree width

directed treewidthThe main motivation of this talk
WHAT ABOUT DIGRAPHS?
Can we do the same thing?
Warning: Not really known much.
Purposes of this talk: report some progress
future direction
and many open questions

Treewidth (T, W) is a tree decomposition of G = (V, E)
 T is a tree, W = {Wt ⊆ V | t ∈ V (T )}W = V , and every edge has both ends in some Wttt∈V (T )

 If t lies one the path in T between t' and t'', then Wt ⊆ Wt ' ∩ Wt ''GT
Ｔree-width:
How close to a Tree
Width=1 ⇔ Tree

Treewidth (T, W) is a tree decomposition of G = (V, E)
 T is a tree, W = {Wt ⊆ V | t ∈ V (T )}W = V , and every edge has both ends in some Wttt∈V (T )

 If t lies one the path in T between t' and t'', then Wt ⊆ Wt ' ∩ Wt '' width of (T, W) := maxt |Wt| - 1
 treewidth of G := min. width over all tree decompositions

GTtreewidth = 2

Ｔree-width:
How close to a Tree
Width=1 ⇔ Tree

Importance of Tree-width (Algorithm) Many hard NP-hard problems can be solved

in linear time.
 (Algorithm) Fixed parameter-tractability (Graph Theory) Great tools in Structure Graph Theory
 (Logic) Courcelle’s theorem: every graph property that is definable in
MSO2 can be decided in linear time for graphs of bounded tree-width!
 (General) AI, Database, Data mining, Social Network, Programming
Language etc.

Treewidth and Grid minor (most important result in treewidth..)Thm (Robertson-Seymour, 1986) The grid minor theorem
For any r, there exists an integer f(r) s.t. for any graph G, either• treewidth of G is ≤ f(r)• G has an r×r -grid-minor
Known resultsO(r5) f(r) =2,f(r) =Ω(r2 log r)(Robertson-Seymour-Thomas [1994], Diestel et al. [1999])

Tree-width r

G contains an H-minor -> H can be obtained from G by deleting edges and contracting edges

Treewidth and Grid minor(most important result in treewidth..)Thm (Robertson-Seymour, 1986) The grid minor theorem
For any r, there exists an integer f(r) s.t. for any graph G, either• treewidth of G is ≤ f(r)• G has an r×r -grid-minor
Known resultsO(r5) f(r) =2,f(r) =Ω(r2 log r)

 G : planar G : bounded genus
 G : H-minor-free G : K3,k-minor-free(Robertson-Seymour-Thomas [1994], Diestel et al. [1999])

f(r) = O(r)f(r) = O(r)(Robertson-Seymour-Thomas [1994])

f(r) = cH・rf(r) = 204k・r(Demaine-Hajiaghayi [2008])(Demaine, Fomin, Hajiaghayi, Thilikos, [2005])(Demaine-Hajiaghayi –KK [2009])

Treewidth and Grid minor(most important result in treewidth..)Thm (Robertson-Seymour, 1986) The grid minor theorem
For any r, there exists an integer f(r) s.t. for any graph G, either• treewidth of G is ≤ f(r)• G has an r×r -grid-minor
Known results f(r) =2O(r5) ,f(r) =Ω(r2 log r)(Robertson-Seymour-Thomas [1994], Diestel et al. [1999])

 G : H-minor-free

f(r) = |V(H)|O(|E(H)|)・r (Kawarabayashi-Kobayashi [2012])

 G : generalf(r) = 2O(r2 log r)(Kawarabayashi-Kobayashi, Leaf-Seymour[2012])

 G: generalf(r) = rO(1)(Chekuri-Chuzoy[2013])

Importance of the grid minor theorem:
1. Fixed Parameter Tractability(FPT) ,bidimetionality(Large vertex cover..)
2. Logic (FOL etc..)
3. Combinatorial Optimization(Routing..)

Structural Results

all graph classes…
The Grid Theorem excluded minors

dynamicprogramming

planartrees

structuraldecomposition(Graph Minor)

tree widthUndirected Graphs

Directed Graphs

all graph classes…
excluded minors

The Grid Theorem

planartrees

tree width

directed tree widthWhat about digraphs?
Seems much harder!
Q.1 What is ``tree-width’’ for digraphs?
Q.2 What is ``minor’’ for digraphs?
What is grid minor for digraphs?
What should be ``grid?
1. Many cycles!
2. Globally connectedTree-width for undirected graphs
1234589671011

Q1. What is Directed Tree-Width?
 Defined analogous to undirected tree width but basedon strong separators
12345896710118 548 568 57

Directed Tree Width

Directed tree-width:
How close to a DAG(directed acyclic graph)
Width=1 ⇔ DAG(Reed’97)

CONJECTURE (Alon, Reed, Robertson, Seymour, Thomas, 1995)
There is a function f such that every digraph of tree-width
at least f(k) has a cylindrical k ×k grid minor.
Directed Grid should be
1. Many cycles
2. Globally connected
3. Directed tree-width
at least kMinor: contract an edge if
only outgoing of tail oronly incoming of head.

CONJECTURE (Alon, Reed, Robertson, Seymour, Thomas, 1995)
There is a function f such that every digraph of tree-width
at least f(k) has a cylindrical k ×k grid minor.

History:
True for planar graphs(Johnson, Robertson, Seymour, Thomas, 99)
True for minor-closed(KK& Kreutzer, SODA’14)
True if ``half-integral’’(KK&Kreuzer’STOC’14)
General case?? -> This is our main result!

Main Theorem (KK and Kreutzer, STOC 2015)
There is a function f such that everydigraph of tree-width at least f(k) has a cylindrical k ×kgrid minor.
Proof > 50 pages….

all graph classes

STRUCTURE THEORYSUMMARY…

Undirected Graphs

Directed Graphs
The Grid Theorem

excluded minors

planartrees

tree width

directed treewidth

Beyond the Euler genus:
Approximating the genus ofgeneral graphs
Ken-ichi Kawarabayashi
NII, Tokyo
Joint work with Anastasios(Tasos) Sidiropoulos
To appear in STOC’15

Surface By a surface, we mean a compact 2-dimensional

manifold.
 We consider plane with crosscaps or handles.
 Plane + crosscap: Projective planar.
 Plane + handle : Torus
 Plane + two crosscaps : Klein bottle

TorusKlein BottleEmbedding into a surface

 Embed graph in a surface with no edge crossings.
 Minor-closed.

 Euler genus of complete graphs and complete

bipartite graphs are known (Heawood 1890!)
 But very little about other graphs….
 Problem(One of original Garey-Johnson)

What is the genus of a given graph? Can you
compute?
 NP-complete to determine Euler genus of a givengraph. (Thomassen, 1988)

Embedding into a surface
 For fixed Euler genus g, O(ng) algorithm. (Filotti,Miller and Reif, 1990)

 O(n3) algorithm. (Robertson and Seymour, 1995)
 Linear time algorithm. (Mohar, 1997)
 Mohar’s algorithm gives either an embedding inthe surface of Euler genus k or an obstruction(One of minimal forbidden minors.)

New Algorithm(FOCS’08)



1.
2.

With B. Reed and B. Mohar
We get another linear time algorithm.
Better in the following sense:
Proof < 25 pages (Mohar’s proof > 100 pages)
Hidden constant is better. But 2gApproximation Algorithm
 No way to compute if g is bigger than log n.
 NP-hard to decide g (Thomassen).
 Trivial approximation: O(n/g).

Euler Formula: |V|-|E|+|F|=2-g → O(n/g)-approximation.

 Essentially nothing is known between NP-hardness and Trivial bound!
 No hardness result is known! (O(1) is NOT ruled out)

Our main result: First ``non-trivial’’ approximation
Theorem: Given a graph G and an integer g, in P, we can either
1. Correctly determine that G cannot be embedded in a surfaceof Euler genus g, or
2. Output an embedding of G in a surface of Euler genus g200
log150 n.
Corollary. O(n1-c)-approximation algorithm to compute Eulergenus
For some small (but absolute constant) c.