10 questions linked to/from NP-hard problems on trees
3k views

### NP-hard problems on paths

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to ...
574 views

### What separates easy global problems from hard global problems on graphs of bounded treewidth?

Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a ...
782 views

### NP-hard problems on cographs

This question is similar to NP-hard problems on trees: There is a large number of NP-complete problems that are tractable on cographs. Are there any known problems that remain NP-complete when ...
635 views

### Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
714 views

### P-complete problems on trees

This question is related to one of my previous questions, NP-hard problems on trees. I am looking for problems that are P-complete on trees.
2k views

### Directed NP-hard problems on DAGs

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
404 views

### In-approximability results in severely restricted graph classes

Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in ...
454 views

### Measuring the connectedness of a graph, and applying it to NP problems

I'm looking for a way to measure how interconnected a graph is. It's well known that graphs can be broken down into connected components. It seems, though, that even in the cases where the graph is ...
This question was motivated by a question asked on stackoverflow. Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$). ...