Linked Questions

22
votes
8answers
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 ...
18
votes
3answers
525 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 ...
12
votes
3answers
753 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 ...
14
votes
4answers
694 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.
12
votes
4answers
1k 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 ...
7
votes
4answers
397 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 ...
22
votes
1answer
543 views

Is there a problem that is easy for cubic graph 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, ...
5
votes
3answers
414 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 ...
11
votes
1answer
279 views

Minimum weight subforest of given cardinality

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$). ...
0
votes
2answers
214 views

NP-hard problems on the class of caterpillars

My question is whether there exist an NP-hard problem that has only a caterpillar as input. By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or ...