I am thinking about the NP-completeness of two graph problems on different graph structures.

For example:

  • The Capacitated Minimum Spanning Tree for graph is NP-hard. However, is the problem still NP-hard for DAG or tree?
  • For Price Collecting Steiner Tree, it's NP-hard for graph. What about for DAG and tree?
  • 1
    $\begingroup$ Can you clarify what your question is? I'm a bit confused by what you mean by "For example" and "I am thinking about..." Is your question just what is listed in the bullet items, or is it something broader? Note we're a question-and-answer sites: we want a well-formed question, not an open-ended prompt/call for discussion about some topic. Can you edit the question to clarify what you're asking? Also, what research have you done? Have you done a literature search (e.g., using Google Scholar)? See cs.stackexchange.com/help/how-to-ask $\endgroup$
    – D.W.
    Nov 1, 2015 at 1:58


Your Answer

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