zbMATH — the first resource for mathematics

Edge-disjoint paths in digraphs with bounded independence number. (English) Zbl 1302.05067
Summary: A digraph \(H\) is infused in a digraph \(G\) if the vertices of \(H\) are mapped to vertices of \(G\) (not necessarily distinct), and the edges of \(H\) are mapped to edge-disjoint directed paths of \(G\) joining the corresponding pairs of vertices of \(G\). The algorithmic problem of determining whether a fixed graph \(H\) can be infused in an input graph \(G\) is polynomial-time solvable for all graphs \(H\) (using paths instead of directed paths). However, the analogous problem in digraphs is NP-complete for most digraphs \(H\). We provide a polynomial-time algorithm to solve a rooted version of the problem, for all digraphs \(H\), in digraphs with independence number bounded by a fixed integer \(\alpha\). The problem that we solve is a generalization of the \(k\) edge-disjoint directed paths problem (for fixed \(k\)).

05C20 Directed graphs (digraphs), tournaments
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Bang-Jensen, J., Edge-disjoint in- and out-branchings in tournaments and related path problems, J. Combin. Theory Ser. B, 51, 1-23, (1991) · Zbl 0659.05052
[2] Chudnovsky, M.; Fradkin, A. O.; Seymour, P., Tournament immersion and cutwidth, J. Combin. Theory Ser. B, 102, 93-101, (2012) · Zbl 1241.05040
[3] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121, (1980) · Zbl 0419.05028
[4] König, D., Über graphen und ihre anwendung auf determinantentheorie und mengenlehre, Math. Ann., 77, 453-465, (1916) · JFM 46.0146.03
[5] Ramsey, F. P., On a problem of formal logic, Proc. Lond. Math. Soc., 30, 264-286, (1930) · JFM 55.0032.04
[6] Robertson, Neil; Seymour, Paul, Graph minors. XIII. the disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[7] Turán, P., Eine extremalaufgabe aus der graphentheorie, Mat. Fiz. Lapok, 48, 436-452, (1941) · JFM 67.0732.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.