89 citations · 484 across the 68 of their papers we have counts for
5 papers · 2 filters
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Dániel Marx, Michał Pilipczuk
Given two graphs and , the Subgraph Isomorphism problem asks if is isomorphic to a subgraph of . While NP-hard in general, algorithms exist for various parameterized…
List H-Coloring a Graph by Removing Few Vertices
Rajesh Chitnis, Laszlo Egri, Daniel Marx
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to…
Finding small patterns in permutations in linear time
Sylvain Guillemot, Dániel Marx
Given two permutations and , the \textsc{Permutation Pattern} problem asks if is a subpattern of . We show that the problem can be solved in time $2^{O(\ell^2\log \el…
A faster FPT algorithm for Bipartite Contraction
Sylvain Guillemot, Dániel Marx
The \textsc{Bipartite Contraction} problem is to decide, given a graph and a parameter , whether we can can obtain a bipartite graph from by at most edge contraction…
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Dániel Marx, László A. Végh
We consider connectivity-augmentation problems in a setting where each potential new edge has a nonnegative cost associated with it, and the task is to achieve a certain connectivi…