Search

For a finite collection of graphs F, the F -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S = V (G) with | S | = k such that G \ S does not contain any of the graphs in F as a topological minor. We prove that for every such F, F -TM-Deletion is fixed parameter tractable on planar graphs. Our algorithm runs in a 2 O(k 2) · n² time, or, alternatively, in 2 O(k) · n4 time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [ABSTRACT FROM AUTHOR]

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding H as a topological subgraph, Partial Dominating Set (find k vertices whose closed neighborhood has maximum size) can be solved in time f(H,k)· nO(1). More significantly, we show that on graphs excluding H as a topological subgraph, Graph Isomorphism can be solved in time nf(H). This result unifies and generalizes two previously known important polynomial time solvable cases of Graph Isomorphism: boundeddegree graphs [E. M. Luks, J. Comput. System Sci., 25 (1982), pp. 42-65] and H-minor free graphs [I. N. Ponomarenko, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147-177, 182]. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition. [ABSTRACT FROM AUTHOR]

We prove that every graph of minimum degree at least r and girth at least 27 contains a subdivision of Kr+1. This implies that the conjecture of Hajós, that every graph of chromatic number at least r contains a subdivision of Kr, is true for graphs of girth at least 27. This conjecture is known to be false in general. [ABSTRACT FROM AUTHOR]