Speaker: |
Kshitij Gajjar (National University of Singapore) |

Organiser: |
Hari Krishnan P A |

Date: |
Friday, 4 Mar 2022, 16:15 to 17:15 |

Venue: |
Via Zoom |

(Scan to add to calendar)

In this talk, we will show how one of these applications can be modelled by a specific class of graphs, and then we will solve SPR for that graph class. We will also show that if we are allowed to change two vertices at a time, then SPR becomes PSPACE-complete, even for a graph class for which SPR is known to be solvable in polynomial time when we are allowed to change only one vertex at a time. This is joint work with Agastya Vibhuti Jha, Manish Kumar and Abhiruk Lahiri (https://arxiv.org/abs/2112.07499).

Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09