I am thinking about the NP-completeness of two graph problems on different graph structures.
- 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?