12 citations · 14 across the 7 of their papers we have counts for
12 papers
Structural Parameterizations for Eternal Vertex Cover
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani +1
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph . To begin with, the defender places guards on vertices of . The attacker, on the…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki +1
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the pre…
Finding -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
Explaining Decisions in ML Models: a Parameterized Complexity Analysis
Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki +1
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the pre…
A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Mueller, Sebastian Ordyniak +2
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that lin…
Classifying Subset Feedback Vertex Set for -Free Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
In the Feedback Vertex Set problem, we aim to find a small set of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires to intersect…
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on -free graphs, that is, graphs that do not contain some fixed graph as an induced subgra…
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Hans Bodlaender, Nick Brettell, Matthew Johnson +3
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…
Bounding the Mim-Width of Hereditary Graph Classes
Nick Brettell, Jake Horsfield, Andrea Munaro +2
A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2
Let , and , respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph . One can a…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
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…