Abstract. We give an approximate Menger-type theorem for the case when a graph [Formula: see text] contains two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that [Formula: see text] is an induced subgraph of [Formula: see text]. More generally, we prove that there exists a function [Formula: see text], such that for every graph [Formula: see text] and [Formula: see text], either there exist two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that the distance between [Formula: see text] and [Formula: see text] is at least [Formula: see text], or there exists [Formula: see text] such that the ball of radius [Formula: see text] centered at [Formula: see text] intersects every [Formula: see text] path.

We study the half-integral $k$-Directed Disjoint Paths Problem ($\tfrac12$kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$, and the input graph is $L$-strongly connected, for any $L\geq 1$. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\geq 2$ there exists $L(k)$ such that $\tfrac12$kDDPP is solvable in time $O(|V(G)|^c)$ for a $L(k)$-strongly connected directed graph $G$. As the function $L(k)$ grows rather quickly, we also show that $\tfrac12$kDDPP is solvable in time $O(|V(G)|^{f(k)})$ in $(36k^3+2k)$-strongly connected directed graphs. We also show that for each $ε<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $εk$.

We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by Maximum Disjoint ℋ-Paths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of Maximum Disjoint ℋ-Paths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a1, …, an, b1, …, bn with ai and bj being adjacent if and only if i ≤ j). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM Disjoint ℋ-Paths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.

We consider the problem of how much edge connectivity is necessary to force a graph $G$ to contain a fixed graph $H$ as an immersion. We show that if the maximum degree in $H$ is $\Delta$, then all the examples of $\Delta$-edge connected graphs which do not contain $H$ as a weak immersion must have a treelike decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique $K_t$ as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain $K_t$ as a strong immersion.

We show how pairs of signed graphs with the same even cycles relate to pairs of grafts with the same even cuts. These results are proved in the more general context of signed binary matroids.

We generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity version. We give polynomial time algorithms for the following problems: 1) the parity H-minor (Odd Kk-minor) containment problem, and 2) the disjoint paths problem with k terminals and the parity condition for each path, as well as several other related problems. We present an O(ma(m, n)n) time algorithm for these problems for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function a(m,n) is the inverse of the Ackermann function (see Tarjan [69]). Note that the first problem includes the problem of testing whether or not a given graph contains k disjoint odd cycles (which was recently solved in [24], [34]), if we fix H to be equal to the graph of k disjoint triangles. The algorithm for the second problem generalizes the Robertson Seymour algorithm for the k-disjoint paths problem. As with the Robertson-Seymour algorithm for the k-disjoint paths problem for any fixed k, in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor. We emphasize that our proof for the correctness of the above algorithms does not depend on the full power of the Graph Minor structure theorem [56]. Although the original Graph Minor algorithm of Robertson and Seymour does depend on it and our proof does have similarities to their arguments, we can avoid the structure theorem by building on the shorter proof for the correctness of the graph minor algorithm in [35]. This work was done as a part of an INRIA-NII collaboration under MOU grant, and partially supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas "New Horizons in Computing" Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, by C & C Foundation, by Kayamori Foundation and by Inoue Research Award for Young Scientists. Consequently, we are able to avoid the much of the heavy machinery of the Graph Minor structure theory. Utilizing some results of [35] and [62], [63], our proof is less than 50 pages.

We prove that for every fixed undirected graph H, there is an O(|V(G)|3) time algorithm that, given a graph G, tests if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)|3) time algorithm that tests if there is an immersion of H into a given graph G. This answers another open question raised by Downey and Fellows in 1992.

At the core of the Robertson-Seymour theory of graph minors lies a powerful decomposition theorem which captures, for any fixed graph H, the common structural features of all the graphs which do not contain H as a minor. Robertson and Seymour used this result to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation, as well as give a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed. The theorem has since found numerous applications, both in graph theory and theoretical computer science. The original proof runs more than 400 pages and the techniques used are highly non-trivial.

At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful theorem which describes the structure of graphs excluding a fixed minor. This result is used to prove Wagner's conjecture and provide a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed (i.e, the Graph Minor Algorithm). However, both results require the full power of the Graph Minor Theory, i.e, the structure theorem.

Let $\mathcal{P}=\{P_1,\dots,P_l\}$ be a set of internally disjoint paths contained in a graph G, and let S be the subgraph defined by $\bigcup_{i=1}^{t}P_i$. A $\mathcal{P}$-bridge is either an edge of $G-E(S)$ with both endpoints in $V(S)$ or a component C of $G-V(S)$ along with all the edges from $V(C)$ to $V(S)$. The attachments of a bridge B are the vertices of $V(B)\cap V(S)$. A bridge B is k-stable if there does not exist a subset of at most $k-1$ paths in $\mathcal{P}$ containing every attachment of B. A classic theorem of Tutte [Graph Theory, Addison–Wesley, Menlo Park, CA, 1984] states that if G is a 3-connected graph, there exists a set of internally disjoint paths $\mathcal{P}'=\{P_1',\dots,P_l'\}$ such that $P_i$ and $P_i'$ have the same endpoints for $1\leq i\leq t$ and every $\mathcal{P}'$-bridge is 2-stable. We prove that if the graph is sufficiently connected, the paths $P_1',\dots,P_l'$ may be chosen so that every bridge containing at least two edges is, in fact, k-stable. We also give several simple applications of this theorem related to a conjecture of Lovász [Problems in Graph Theory, Recent Advances in Graph Theory, M. Felder, ed., Acadamia, Prague, 1975] on deleting paths while maintaining high connectivity.