### Abstract

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 α. The problem that we solve is a generalization of the k edge-disjoint directed paths problem (for fixed k).

Original language | English (US) |
---|---|

Pages (from-to) | 19-46 |

Number of pages | 28 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 110 |

DOIs | |

State | Published - Jan 1 2015 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Digraphs
- Disjoint paths
- Independence number
- Linking problem
- Polynomial-time algorithm
- Tournaments