Graph minors. XIII: The disjoint paths problem
From MaRDI portal
Publication:1892832
DOI10.1006/jctb.1995.1006zbMath0823.05038OpenAlexW2005079828WikidataQ55881137 ScholiaQ55881137MaRDI QIDQ1892832
Publication date: 2 July 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1995.1006
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Planar Disjoint-Paths Completion, Kernel Bounds for Path and Cycle Problems, Linkage for the diamond and the path with four vertices, Uniform Kernelization Complexity of Hitting Forbidden Minors, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Some notes on bounded starwidth graphs, Towards the Graph Minor Theorems for Directed Graphs, Induced disjoint paths in circular-arc graphs in linear time, Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs, On the Pathwidth of Almost Semicomplete Digraphs, Detecting induced star-like minors in polynomial time, Fixed-Parameter Tractability, A Prehistory,, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, What’s Next? Future Directions in Parameterized Complexity, On the kernelization of split graph problems, Finding Two Edge-Disjoint Paths with Length Constraints, Bounded fixed-parameter tractability and reducibility, Boxicity and treewidth, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement, Finding cycles and trees in sublinear time, Reducing Rank of the Adjacency Matrix by Graph Modification, Excluding Kuratowski graphs and their duals from binary matroids, A polynomial-time algorithm for outerplanar diameter improvement, The terminal-pairability problem in complete bipartite graphs, The power of cut-based parameters for computing edge-disjoint paths, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, Forbidding Kuratowski Graphs as Immersions, On the satisfiability of quantum circuits of small treewidth, Linking four vertices in graphs of large connectivity, Hadwiger Number of Graphs with Small Chordality, Simple undirected two-commodity integral flow with a unitary demand, Detecting an induced subdivision of \(K_{4}\), Geodesic geometry on graphs, FPT algorithms to compute the elimination distance to bipartite graphs and more, On the maximum degree of path-pairable planar graphs, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, Graph coloring with no large monochromatic components, Wheel-Free Deletion Is W[2-Hard], The Induced Disjoint Paths Problem, An Improved Algorithm for Finding Cycles Through Elements, Improved kernels for tracking paths, The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases, The \(k\)-in-a-path problem for claw-free graphs, Obtaining a planar graph by vertex deletion, Optimal connectivity for fat-triangle linkages, On the robustness of potential-based flow networks, Embedding of complete graphs in broken Chimera graphs, A tight lower bound for edge-disjoint paths on planar DAGs, Packing \(A\)-paths of length zero modulo a prime, Graph theory. Abstracts from the workshop held January 2--8, 2022, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, The Excluded Minors for Isometric Realizability in the Plane, Multiflow Feasibility: An Annotated Tableau, Single-Sink Multicommodity Flow with Side Constraints, Typical sequences revisited -- computing width parameters of graphs, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, The theory of guaranteed search on graphs, Parameters Tied to Treewidth, Square roots of minor closed graph classes, Graphs with no 7-wheel subdivision, Adiabatic quantum programming: minor embedding with hard faults, Recent Progress on Well-Quasi-ordering Graphs, Finding k Partially Disjoint Paths in a Directed Planar Graph, Vertex-minor reductions can simulate edge contractions, Decomposition of structural learning about directed acyclic graphs, Shortest node-disjoint paths on random graphs, Edge Contractions in Subclasses of Chordal Graphs, Tight Bounds for Linkages in Planar Graphs, Linkability in iterated line graphs, Unnamed Item, Approximating clique-width and branch-width, Vertex disjoint paths on clique-width bounded graphs, Hitting Forbidden Minors: Approximation and Kernelization, A $c^k n$ 5-Approximation Algorithm for Treewidth, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, Graph minor theory, On the odd-minor variant of Hadwiger's conjecture, Excluding a group-labelled graph, DAG-Width and Circumference of Digraphs, Complexity of a classical flow restoration problem, Routing in Undirected Graphs with Constant Congestion, On linkages in polytope graphs, New Hardness Results for Routing on Disjoint Paths, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Faster Computation of Path-Width, Partitioning Graphs into Connected Parts, Mine ’Em All: A Note on Mining All Graphs, FPT is characterized by useful obstruction sets, Finding good tree decompositions by local search, Highly linked graphs, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, Euler Digraphs, Planar Digraphs, The first order definability of graphs with separators via the Ehrenfeucht game, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Parameterized computation and complexity: a new approach dealing with NP-hardness, Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs, Steiner Problems with Limited Number of Branching Nodes, Algorithms for finding disjoint path covers in unit interval graphs, Chordless paths through three vertices, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, Tractability in constraint satisfaction problems: a survey, Edge-disjoint odd cycles in 4-edge-connected graphs, Cyclability in graph classes, (Total) vector domination for graphs with bounded branchwidth, Excluded-minor characterization of apex-outerplanar graphs, Contraction obstructions for connected graph searching, Computing directed pathwidth in \(O(1.89^n)\) time, Approximate tree decompositions of planar graphs in linear time, Small complete minors above the extremal edge density, The label cut problem with respect to path length and label frequency, Approximation algorithms for treewidth, Bounded face-width forces \(K_7\)-minors in orientable surfaces, Coloring immersion-free graphs, Planar disjoint-paths completion, Quickly deciding minor-closed parameters in general graphs, Differential geometric treewidth estimation in adiabatic quantum computation, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Reducing rank of the adjacency matrix by graph modification, Graph editing to a fixed target, Irrelevant vertices for the planar disjoint paths problem, On the Hadwiger's conjecture for graph products, Some recent progress and applications in graph minor theory, The density maximization problem in graphs, Detecting induced minors in AT-free graphs, Kernel bounds for path and cycle problems, Parameterized complexity of vertex deletion into perfect graph classes, Effective computation of immersion obstructions for unions of graph classes, Rooted \(K_4\)-minors, Immersion in four-edge-connected graphs, Practical algorithms for branch-decompositions of planar graphs, The disjoint paths problem in quadratic time, Graph minors. XXII. Irrelevant vertices in linkage problems, A linear time algorithm for the induced disjoint paths problem in planar graphs, On graph contractions and induced minors, The complexity of minimum convex coloring, Linkless and flat embeddings in 3-space, Edge contractions in subclasses of chordal graphs, A combinatorial optimization algorithm for solving the branchwidth problem, Graph operations on parity games and polynomial-time algorithms, On shortest disjoint paths in planar graphs, Satisfiability, branch-width and Tseitin tautologies, Complexity evaluation of benchmark instances for the \(p\)-median problem, On the maximum disjoint paths problem on edge-colored graphs, Kernel bounds for disjoint cycles and disjoint paths, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Packing cycles through prescribed vertices under modularity constraints, Paths of bounded length and their cuts: parameterized complexity and algorithms, Subexponential parameterized algorithms, On partitioning a graph into two connected subgraphs, Faster parameterized algorithms for minor containment, Detecting an induced net subdivision, A new algorithm for finding trees with many leaves, Confronting intractability via parameters, Algorithms for finding an induced cycle in planar graphs, Treewidth lower bounds with brambles, Edge-disjoint paths in digraphs with bounded independence number, Criticality for multicommodity flows, Practical algorithms for MSO model-checking on tree-decomposable graphs, Finding a subdivision of a digraph, The hardness of routing two pairs on one face, Disjoint paths in tournaments, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Parameterized algorithms for list \(K\)-cycle, Computing tree-depth faster than \(2^n\), Finding disjoint paths in split graphs, A simple linear-time algorithm for finding path-decompositions of small width, Fixed-parameter tractability and completeness II: On completeness for W[1], Mixed searching and proper-path-width, Forbidden directed minors and Kelly-width, Advice classes of parametrized tractability, The extremal function for 3-linked graphs, Primal-dual approximation algorithms for integral flow and multicut in trees, Some open problems on excluding a uniform matroid, \(K_{6}\) minors in large 6-connected graphs, A new proof of the flat wall theorem, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Locally planar graphs are 5-choosable, MSOL restricted contractibility to planar graphs, Connected graph searching, Trichotomies in the complexity of minimal inference, Treewidth computations. I: Upper bounds, Graph minors XXIII. Nash-Williams' immersion conjecture, Finite planar emulators for \(K_{4,5} - 4K_{2}\) and \(K_{1,2,2,2}\) and Fellows' conjecture, Induced disjoint paths problem in a planar digraph, Disjoint paths in sparse graphs, Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design, Monadic second-order model-checking on decomposable matroids, Finding odd cycle transversals., Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Minimal multicut and maximal integer multiflow: a survey, Multiflows in symmetric digraphs, Explicit bounds for graph minors, Shortest \((A+B)\)-path packing via hafnian, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Combinatorial optimization with 2-joins, Containment relations in split graphs, Min-sum 2-paths problems, The structure of obstructions to treewidth and pathwidth, The parametrized complexity of knot polynomials, Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, Adapting the directed grid theorem into an \textsf{FPT} algorithm, Rooted minor problems in highly connected graphs, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Computing crossing numbers in quadratic time, On search, decision, and the efficiency of polynomial-time algorithms, Excluding subdivisions of bounded degree graphs, Modulo orientations and matchings in graphs, Rooted routing in the plane, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], An analysis of the parameterized complexity of periodic timetabling, Linkage on the infinite grid, Optimizing adiabatic quantum program compilation using a graph-theoretic framework, Graph minors. VII: Disjoint paths on a surface, Structural parameterizations with modulator oblivion, String graphs. II: Recognizing string graphs is NP-hard, Space-efficient vertex separators for treewidth, Distance from triviality 2.0: hybrid parameterizations, String graphs. I: The number of critical nonstring graphs is infinite, Finding a path with two labels forbidden in group-labeled graphs, The tree-width of C, Mim-width. I. Induced path problems, On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory, On interval routing schemes and treewidth, Removable circuits in multigraphs, Note on the hardness of generalized connectivity, Hypertree-depth and minors in hypergraphs, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, The complete set of minimal simple graphs that support unsatisfiable 2-CNFs, A model for finding transition-minors, Subexponential algorithms for partial cover problems, Polynomial kernels for hitting forbidden minors under structural parameterizations, Size-treewidth tradeoffs for circuits computing the element distinctness function, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph, On the edge capacitated Steiner tree problem, Towards tight(er) bounds for the excluded grid theorem, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, An improvement of Reed's treewidth approximation, Explicit linear kernels for packing problems, Packing and covering immersions in 4-edge-connected graphs, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Detecting fixed patterns in chordal graphs in polynomial time, Self-witnessing polynomial-time complexity and prime factorization, On the complexity of finding iso- and other morphisms for partial \(k\)- trees, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Fast minor testing in planar graphs, On the complexity of the identifiable subgraph problem, Complexity of path-forming games, Half-integral packing of odd cycles through prescribed vertices, A trichotomy for regular simple path queries on graphs, Finding large cycles in Hamiltonian graphs, An improved linear edge bound for graph linkages, Chordal deletion is fixed-parameter tractable, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\), Packing cycles through prescribed vertices, New algorithms for maximum disjoint paths based on tree-likeness, On structural parameterizations of the edge disjoint paths problem, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Disjoint paths in symmetric digraphs, A polynomial-time algorithm to find a linkless embedding of a graph, Minor-embedding in adiabatic quantum computation. I: The parameter setting problem, Two disjoint shortest paths problem with non-negative edge length, The undirected two disjoint shortest paths problem, The linkedness of cubical polytopes: the cube, Induced disjoint paths in AT-free graphs, On tree-connectivity and path-connectivity of graphs, The directed 2-linkage problem with length constraints, A relaxation of the directed disjoint paths problem: a global congestion metric helps, Approximating the maximum clique minor and some subgraph homeomorphism problems, All structured programs have small tree width and good register allocation, Upper bounds on the size of obstructions and intertwines, Linear connectivity forces large complete bipartite minors, Graph minors. XXI. graphs with unique linkages, Note on coloring graphs without odd-\(K_k\)-minors, A partial k-arboretum of graphs with bounded treewidth, A lower bound on the tree-width of graphs with irrelevant vertices, On width measures and topological problems on semi-complete digraphs, Structure and recognition of graphs with no 6-wheel subdivision, The complexity of mixed-connectivity, Partitioning graphs into connected parts, Disjoint directed and undirected paths and cycles in digraphs, Minimum degree condition for a graph to be knitted, An exact algorithm for subgraph homeomorphism, Two edge-disjoint paths with length constraints, Algorithms and obstructions for linear-width and related search parameters, Alternating paths in edge-colored complete graphs, Directed tree-width, Graphs with magnetic Schrödinger operators of low corank, Parameterized complexity of set-restricted disjoint paths on chordal graphs, Few induced disjoint paths for \(H\)-free graphs, On the complexity of database queries, Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation, Fixed-parameter tractability for subset feedback set problems with parity constraints, Embeddings of graphs, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Packing cycles in undirected group-labelled graphs, Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs, The complexity of contracting bipartite graphs into small cycles, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Parameterizing path partitions, Combing a Linkage in an Annulus, On the bond polytope, Cycle lengths in randomly perturbed graphs, On the complexity of the bilevel minimum spanning tree problem, The firebreak problem, Solving the edge‐disjoint paths problem using a two‐stage method, Edge-treewidth: algorithmic and combinatorial properties, Steiner connectivity problems in hypergraphs, Optimal sufficient requirements on the embedded Ising problem in polynomial time, First-order Logic with Connectivity Operators, Tangle bases: Revisited, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, Arkhipov's theorem, graph minors, and linear system nonlocal games, Directed Steiner tree packing and directed tree connectivity, Detours in directed graphs, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, On Interval Routing Schemes and treewidth, Packing topological minors half‐integrally, On the logical strength of the better quasi order with three elements, Approximating maximum integral multiflows on bounded genus graphs, Excluding a planar matching minor in bipartite graphs, A graph minor condition for graphs to be \(k\)-linked, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, A survey of parameterized algorithms and the complexity of edge modification, Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, How to build a pillar: a proof of Thomassen's conjecture, Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths, Planarizing graphs and their drawings by vertex splitting, The linkedness of cubical polytopes: beyond the cube, A lower bound for treewidth and its consequences, Rankings of graphs, A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups, Almost disjoint paths and separating by forbidden pairs, Minor embedding in broken chimera and derived graphs is NP-complete, Unnamed Item, Contracting to a longest path in H-free graphs, Few induced disjoint paths for \(H\)-free graphs, Parameterized algorithms for finding highly connected solution, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Computing Tree Decompositions, An Improvement of Reed’s Treewidth Approximation, The pathwidth and treewidth of cographs, Parametric problems on graphs of bounded tree-width, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Frames, $A$-Paths, and the Erdös--Pósa Property, Rolling backwards can move you forward: On embedding problems in sparse expanders, Polynomial-time self-reducibility: theoretical motivations and practical results∗, Unnamed Item, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs, Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, Finding disjoint paths with different path-costs: Complexity and algorithms, Shortest edge-disjoint paths in graphs, The parallel complexity of tree embedding problems (extended abstract), Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs, Adapting the Directed Grid Theorem into an FPT Algorithm, Mineurs d'arbres avec racines, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, Obtaining a Planar Graph by Vertex Deletion, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Maximum Cut Parameterized by Crossing Number, The Parameterized Complexity of Motion Planning for Snake-Like Robots, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Finding an induced subdivision of a digraph, Unnamed Item, Kernelization of Two Path Searching Problems on Split Graphs, The size of an intertwine, Minimum Bisection Is Fixed-Parameter Tractable, Connectivity and inference problems for temporal networks, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Parallel algorithms with optimal speedup for bounded treewidth, An Algorithm for Detecting Intrinsically Knotted Graphs, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, Slightly Superexponential Parameterized Problems, A sufficiently fast algorithm for finding close to optimal clique trees, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, Induced Disjoint Paths in Claw-Free Graphs, Half-integral linkages in highly connected directed graphs, Graphs with the Circuit Cover Property, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, Unnamed Item, Unnamed Item, A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Contracting bipartite graphs to paths and cycles, The communication complexity of enumeration, elimination, and selection, Clique-width and well-quasi-ordering of triangle-free graph classes, Contracting bipartite graphs to paths and cycles, Two strikes against perfect phylogeny, Linkless embeddings of graphs in 3-space, The Parameterized Complexity of Graph Cyclability, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Disjoint paths and connected subgraphs for \(H\)-free graphs, Disjoint paths and connected subgraphs for \(H\)-free graphs, On the approximability of time disjoint walks, Parameterized algorithms for finding highly connected solution, Unnamed Item, Unnamed Item, Block elimination distance, Walking through waypoints, Unnamed Item, The parameterized complexity of cycle packing: indifference is not an issue, Block elimination distance, The computational complexity of graph contractions II: Two tough polynomially solvable cases, A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps., Elimination Distance to Bounded Degree on Planar Graphs, Finding a Small Number of Colourful Components, Modification to Planarity is Fixed Parameter Tractable, Lean Tree-Cut Decompositions: Obstructions and Algorithms, Packing Cycles Faster Than Erdos--Posa, Algorithmic Applications of Tree-Cut Width, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, Unnamed Item, Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Kernelization: New Upper and Lower Bound Techniques, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Optimal Construction of Edge-Disjoint Paths in Random Graphs, The Directed Disjoint Shortest Paths Problem, A Linear-Time Parameterized Algorithm for Node Unique Label Cover, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Unnamed Item, Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems, Disjoint Paths in Decomposable Digraphs
