I need to show that deciding whether a graph G has at most 2017 strongly connected components in in NL.

After searching, i found a previous answer:

Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

The answer there by yuval filmus was given for verifying an exact amount of SCCs.

I am not sure how to modify it to make at applicable for checking an "at most" condition.

I though of running the given algorithm for a loop of t:=1 to 2017, where t is the number of SCCs. the loop continues until an acceptable t is found and the algorithm accepts. if none is found, the algorithm rejects. the result still seems to be in NL becuase i use the same amount of memory and add a loop counter for t.

Is this the correct path?

thank you.

  • $\begingroup$ The only way to know if this is the correct path is to try it out. $\endgroup$ Commented Nov 19, 2016 at 12:40
  • $\begingroup$ @YuvalFilmus, not sure what you mean by that... what does "try it out" mean here? $\endgroup$
    – AmirB
    Commented Nov 19, 2016 at 13:24
  • 2
    $\begingroup$ You actually already tried it out, having a complete solution inside your post. If you are asking whether your solution is correct, ask your TA instead. $\endgroup$ Commented Nov 19, 2016 at 13:30
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Nov 19, 2016 at 16:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.