An exact characterization of tractable demand patterns for maximum disjoint path problems

DOI10.1137/1.9781611973730.44MaRDI QIDQ5363090zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Paul Wollan

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.0871, http://real.mtak.hu/31191/1/marx_wollan_soda2015_paths_u.pdf

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the following general disjoint paths problem: given a supply graph $G$, a set $TsubseteqV(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 $mathcalH$ of graphs, we denote by $mathcalH$-Maximum Disjoint Paths the restriction of this problem when the demand graph $H$ is assumed to be a member of $mathcalH$. 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 $mathcalH$-Maximum Disjoint Paths for every hereditary class $mathcalH$ 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 $a_1$, $dots$, $a_n$, $b_1$, $dots$, $b_n$ with $a_i$ and $b_j$ being adjacent if and only if $ilej$). Specifically, we prove the following classification for every hereditary class $mathcalH$. 1. If $mathcalH$ does not contain every matching and does not contain every skew biclique, then $mathcalH$-Maximum Disjoint Paths is FPT. 2. If $mathcalH$ does not contain every matching, but contains every skew biclique, then $mathcalH$-Maximum Disjoint Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the ErdH{o}s-P'osa property. 3. If $mathcalH$ contains every matching, then $mathcalH$-Maximum Disjoint Paths is W[1]-hard and the valid paths do not satisfy the analog of the ErdH{o}s-P'osa property.

Recommendations

• The Induced Disjoint Paths Problem
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• On the disjoint paths problem
• scientific article; zbMATH DE number 4191702

Cited in

(4)

• Recent techniques and results on the Erdős-Pósa property
• Structured connectivity augmentation
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)

This page was built for publication: An exact characterization of tractable demand patterns for maximum disjoint path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363090)