Finding induced acyclic subgraphs in random digraphs
type: Item
instance of: scholarly article
title: Finding induced acyclic subgraphs in random digraphs
zbMATH Open document ID: 1031.05119
author: C. R. Subramanian
published in: The Electronic Journal of Combinatorics
publication date: 2004-02-05T00:00:00Z
full work available at URL: https://eudml.org/doc/123241
full work available at URL: v10i1r46.html
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 2038344
zbMATH Keywords: optimization
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2038344