22 citations · 107 across the 16 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
math.CO2017★ 11 cited
On inverse powers of graphs and topological implications of Hedetniemi's conjecture
Marcin Wrochna
We consider a natural graph operation that is a certain inverse (formally: the right adjoint) to taking the k-th power of a graph. We show that it preserves the topology (the…
cs.DS2017
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers…
cs.DS2017
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…