Circumventing Connectivity for Kernelization

Pallavi Jain IIT Jodhpur

Lawqueen Kanesh National University of Singapore

Shivesh K. Roy Eindhoven University of Technology

Saket Saurabh IMSc Chennai & Univ. of Bergen

Roohani Sharma Max Planck Institute for Informatics

CIAC 2021�May 10-12^th 2021 , Cyprus

Practical motivation

• Posed by a real newspaper company of Buenos Aires
• Task: Deliver newspapers to the subscribers by a truck that stops at street crossings
• Goal: Minimize the length of tour driven by the truck
• Studied by Donne and Tagliavini from the approximation algorithm perspective

​

2

[Donne & Tagliavini 2018]

Formally

Theoretical motivation

• Classical vertex subset problems demanding “connectivity” have gained a lot of attention in the paradigm of parameterized complexity
• Two of the well studied problem in this stream are Connected Vertex Cover (CVC) and Connected Feedback Vertex Set (CFVS)
• Both the problems are fixed-parameter tractable (FPT)
• But “hard” from the kernelization point-of-view

4

Is there a “specific” connectivity constraint that bring us back to the world of polynomial kernel?

?

Problem definitions

5

Problem definitions

6

Results

7

FVS preserving subgraph

8

CW-FVS kernelization algorithm

Intuitively the algorithm works as follows

​

9

Lower bound for CW-SFVS

10

C

Polynomial-time parameter preserving reduction

11

Conclusion

• When we demand closed walk constraint on the solution of VC and FVS, then they exhibit a polynomial kernels unlike their connected counterparts viz. CVC and CFVS

Open problems:

1. Generalize these results for directed graphs
2. Give a dichotomy of the vertex deletion problems that admit polynomial kernels with the closed walk constraint
3. What happens to the kernelization complexity of these classical vertex deletion problems, when other “specific connectivity” constraints are demanded from the solution?

​

12

THANK YOU!

​