Header menu link for other important links
X
Hitting topological minors is FPT
F.V. Fomin, D. Lokshtanov, , S. Saurabh, M. Zehavi
Published in Association for Computing Machinery
2020
Pages: 1317 - 1326
Abstract
In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G, a family of undirected graphs F and an integer k. The task is to determine whether G contains a set of vertices S of size at most k, such that the graph Gg- S obtained from G by removing the vertices of S, contains no graph from F as a topological minor. We give an algorithm forTM-Deletion with running time f(hg,k)· |V(G)|4. Here hg is the maximum size of a graph in F and f is a computable function of hg and k. This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and hg. © 2020 ACM.
About the journal
JournalData powered by TypesetProceedings of the Annual ACM Symposium on Theory of Computing
PublisherData powered by TypesetAssociation for Computing Machinery
ISSN07378017