Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học:Finding Induced Acyclic Subgraphs in Random Digraphs

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 ) for some 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 n1+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 | Finding Induced Acyclic Subgraphs in Random Digraphs C.R. Subramanian The Institute of Mathematical Sciences Taramani Chennai - 600 113 India. crs@imsc.res.in Submitted Oct 22 2001 Accepted Aug 18 2003 Published Dec 4 2003 MR Subject Classifications 05C80 68W40 Abstract 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 ỡ ne for some e 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 n1 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. 1 Introduction Given a simple digraph D V E we want to find a V c V of as large size I V l as possible such that the induced subgraph D V is acyclic. By simple we mean that there is at most one arc directed edge between any unordered pair of vertices. Self-loops are not allowed. Throughout we mean vertex induced subgraphs whenever we use the term subgraphs. The decision version Is V k is NP-complete 3 . The optimization version is not polynomial-time approximable even within a multiplicative ratio of O n for some e 0 unless P NP 4 . We show that if D is a random digraph obtained by randomly choosing the arcs then the size of any maximal solution is almost surely within a ratio of o ln n from the optimal solution. Except for very sparse random digraphs obtained by choosing the arcs with probability n-1 o 1 the ratio is in fact O 1 . Thus for random digraphs one can obtain a significant improvement in the quality of approximation. We assume that V 1 . n for the rest of the paper. Also p 0.5 is a positive real number. The random model is defined in the following way. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R46 1 Model D E D n p Choose .