Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
From MaRDI portal
Publication:7260679
Cites work
- A note on multiflows and treewidth
- A parameterized approximation scheme for min k-cut
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- Almost polynomial factor inapproximability for parameterized k-clique
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- An exponential time parameterized algorithm for planar disjoint paths
- Approximating disjoint-path problems using packing integer programs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Baby PIH: Parameterized inapproximability of min CSP
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Constant approximating k-clique is w[1]-hard
- Constant approximating Parameterized \(k\)-\textsc{SetCover} is W[2]-hard
- Directed tangle tree-decompositions and applications
- Distributed algorithms for computing shortest pairs of disjoint paths
- Edge-disjoint paths in planar graphs
- Edge-disjoint paths in planar graphs with constant congestion
- Finding disjoint paths in split graphs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 5899246 (Why is no real title available?)
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 6851840 (Why is no real title available?)
- Improved approximation for node-disjoint paths in planar graphs
- Irrelevant vertices for the planar disjoint paths problem
- Negative association of random variables, with applications
- New hardness results for routing on disjoint paths
- On routing disjoint paths in bounded treewidth graphs
- On the Parameterized Complexity of Approximating Dominating Set
- On the parameterized intractability of determinant maximization
- Parameterized algorithm for the disjoint path problem on planar graphs: exponential in k^2 and linear in n
- Parameterized algorithms
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Parameterized inapproximability for Steiner orientation by gap amplification
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
- Planar disjoint paths, treewidth, and kernels
- Pre-reduction graph products: hardnesses of properly learning DFAs and approximating EDP on DAGs
- Rooted routing in the plane
- The directed grid theorem
- The directed subgraph homeomorphism problem
- The disjoint paths problem in quadratic time
- The PCP theorem by gap amplification
- The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
Cited in
(2)
This page was built for publication: Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260679)
