home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1860 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  1.3 KB
  1. Path: sparky!uunet!mcsun!uknet!stl!sbil!wet!spitws75!tdk
  2. From: tdk@spitws75.sbil.co.uk (Tim Kempster)
  3. Newsgroups: comp.theory
  4. Subject: Constructive proof of directed graph unconectivity
  5. Keywords: CON NLOG NLOG-Complete
  6. Message-ID: <1992Sep3.161109.22586@sbil.co.uk>
  7. Date: 3 Sep 92 16:11:09 GMT
  8. Sender: news@sbil.co.uk
  9. Reply-To: tdk@spitws75.sbil.co.uk
  10. Organization: Salomon Brothers International Limited
  11. Lines: 28
  12.  
  13. I am trying to find an alogrithm with NLOG complexity for the 
  14. problem defined below. 
  15.  
  16. UNCON
  17. INSTANCE: A directed graph G=(V,A), two vertices u,v \in V
  18. QUESTION: Is there no path from u to v in G ?
  19.  
  20.  
  21. This is the complement of the problem CON which has the same instance
  22. and asks, "Is there a path u to v ? ". This problem has an NLOG 
  23. solution and is infact NLOG complete w.r.t LOG space reduction. 
  24.  
  25. Immerman and Szelepcsenyi have shown NLOG = CO-NLOG so combining these
  26. results we see UNCON is indeed in NLOG.
  27.  
  28. Is there a direct constructive proof of this fact ?
  29.  
  30. That is is there a Turing Machine algorithm (non-deterministic 
  31. log space) which can resolve this question. I was thinking along the lines
  32. of transforming an instance of UNCON into CON by taking the complement 
  33. of G or the complement of the transitive closure ? A bit vaugue I know.
  34.  
  35. The proof that CON is in NLOG gives the algorithm for a TM explicitly. 
  36.  
  37.  
  38. Can anyone help ?
  39.  
  40. Tim Kempster
  41.