Finding induced acyclic subgraphs in random digraphs
Summary: Consider the problem of finding a large induced acyclic subgraph of a given simple digraph \(D=(V,E)\). The decision version of this problem is NP-complete and its optimization is not likely to be approximable within a ratio of \(O(n^{\varepsilon})\) for some \(\varepsilon > 0\). We study this problem when \(D\) is a random instance. We show that, almost surely, any maximal solution is within an \(o(\ln n)\) factor from the optimal one. In addition, except when \(D\) is very sparse (having \(n^{1+o(1)}\) edges), this ratio is in fact \(O(1)\). Thus, the optimal solution can be approximated in a much better way over random instances.
- Improved bounds on induced acyclic subgraphs in random digraphs
- Induced acyclic subgraphs in random digraphs: improved bounds
- On the size of induced acyclic subgraphs in random digraphs
- Largest induced acyclic tournament in random digraphs: a 2-point concentration
- Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms
- Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms
- Improved bounds on induced acyclic subgraphs in random digraphs
- On induced acyclic subgraphs in sparse random digraphs
- Largest induced acyclic tournament in random digraphs: a 2-point concentration
- On the size of induced acyclic subgraphs in random digraphs
- A classification of isomorphism-invariant random digraphs
This page was built for publication: Finding induced acyclic subgraphs in random digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422133)
