1 of 10

 

Bart M. P. Jansen

Shivesh K. Roy

IPEC 2023

2 of 10

  •  

2

2

1

2

2

2

1

 

1

 

 

[Bodlaender et al.’ J. ACM 16]

[Ahn et al.’ arXiv 22]

 

[Kirkpatrick & Hell’ SICOMP 83]

3 of 10

The world of Sparse Graphs

​

​

​

3

[Picture by Felix Reidl]

 

 

4 of 10

  •  

4

Sunflower

 

 

 

 

 

 

[Erdos-Rado’ J. Lond. Math. Soc. 60]

 

5 of 10

  •  

5

 

 

 

 

 

 

 

 

 

6 of 10

  •  

6

Projection

 

 

 

 

 

[Drange et al.’ STACS 16]

 

 

[Drange et al.’ STACS 16]

7 of 10

​

​

​

​

7

Kernel for (Unweighted) Triangle Packing on Bounded Expansion Graphs

 

 

 

 

 

 

 

 

 

 

 

 

 

[Drange et al.’ STACS 16]

 

 

 

 

 

 

 

 

 

 

[Drange et al.’ STACS 16]

4. Apply Sunflower lemma on each equivalence class.

8 of 10

​

​

​

​

8

Kernel for (Unweighted) Triangle Packing on Bounded Expansion Graphs

 

4. Apply Sunflower lemma on each equivalence class.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9 of 10

  •  

9

Summary

Open Problem

10 of 10

​

​

​

​

10

Kernel for (Unweighted) Triangle Packing on Bounded Expansion Graphs

 

4. Apply Sunflower lemma on each equivalence class.