On the Parameterized Complexity of Multiway Near-Separator

Bart M. P. Jansen

Shivesh K. Roy

IPEC 2023

2

[Marx’ TCS 06]

[Dahlhaus et al.’ STOC 92]

3

​

​

​

​

​

​

​

​

​

​

​

• The size of a minimum Multiway Separator can be arbitrary large compared to the size of a minimum Multiway Near-separator.

4

Size of Near-separator vs Separator

Multiway Near-separator

Multiway Separator

[Jansen, R.]

5

Pushing Lemma

Multiway Near-Separator

[Jansen, R.]

6

Algorithm for Multiway Near-Separator

[Jansen, R.]

​

​

​

​

​

​

​

​

​

​

7

Bounding Number of Terminals

8

Towards Bounding Number of Terminals

[Thomasse’ TALG 10]

[Jansen, R.]

9

Summary

Open Problems