38 citations · 246 across the 68 of their papers we have counts for
7 papers · 2 filters
Connected Vertex Cover for -Free Graphs
Matthew Johnson, Giacomo Paesani, Daniel Paulusma
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most that induces a connected subgraph of . This is a well-studied problem, known…
Independent Feedback Vertex Set for -free Graphs
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer , to delete at most vertices from a given graph so t…
Independent Feedback Vertex Sets for Graphs of Bounded Diameter
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets and , where is an independent set and induces…
Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
We continue research into a well-studied family of problems that ask whether the vertices of a graph can be partitioned into sets and~, where is an independent set and $…
Contraction and Deletion Blockers for Perfect Graphs and -free Graphs
Öznur Yaşar Diner, Daniël Paulusma, Christophe Picouleau +1
We study the following problem: for given integers , and graph , can we reduce some fixed graph parameter of by at least via at most graph operations from…
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…
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +2
Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem i…