Tata Institute of Fundamental Research
Singly Connected Vertex Deletion Problem
STCS Student Seminar
Speaker:
Avinandan Das (Institut de Recherche en Informatique Fondamentale, Paris)
Organiser:
Prabhat Kumar Jha
Date:
Friday, 23 Apr 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
In this talk, I am going to present the Singly Connected Vertex Deletion Problem (SCVD).
A digraph D is singly connected if for all ordered pairs of vertices u, v ∈ V (D), there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a positive integer k, does there exist a set S ⊆ V (D) such that |S| ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP-hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic kernel.
We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear kernel.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Avinandan Das (Institut de Recherche en Informatique Fondamentale, Paris) |
| Organiser: | Prabhat Kumar Jha |
| Date: | Friday, 23 Apr 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
In this talk, I am going to present the Singly Connected Vertex Deletion Problem (SCVD).
A digraph D is singly connected if for all ordered pairs of vertices u, v ∈ V (D), there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a positive integer k, does there exist a set S ⊆ V (D) such that |S| ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP-hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic kernel.
We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear kernel.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
A digraph D is singly connected if for all ordered pairs of vertices u, v ∈ V (D), there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a positive integer k, does there exist a set S ⊆ V (D) such that |S| ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP-hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic kernel.
We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear kernel.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09