Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity

Nina Chiarelli, Tatiana R. Hartinger, Matthew Johnson +2

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Trans…