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 edges) or specially chosen vertex (or edge) or anything like that is part of the input.

Instance: a caterpillar $T$
Question: __________

There are two similar question in the site: NP-hard problems on trees, NP-hard problems on paths. Note that all answers for the latter problem needs more than one path in input and/or additional structures (edges weights, for instance). In fact, so are most (but not all) answers of the former problem (on trees) as well.

I feel that it is implausible to have an NP-hard problem that take only a path as input. But, it is possible to have an NP-complete problem that take only a caterpillar as input (isn't it?).

Update: I am interested in problems that are naturally defined on caterpillars. True, we cannot define naturality: but we can sense it when we see it.

Thank you
A caterpillar is equivalent to a list of integers $n_1,n_2,...,n_m$ (given in unary), in which integer $n_i$ represents a central node $i$ and its $n_i$ neighbours.

So your question could be rephrased: "Are there hard problems in which the input is a list of (unary) integers?"

Clearly this is cheating, but a list of integers can encode everything (e.g. a binary number $(0,1,0,0,1,1,0,1)$, a string, a graph, ...), so given a polynomial time instance decoding/encoding algorithm, every problem (in particular all NP-complete problems) can be translated to a problem on a single caterpillar; note that this is not valid for problems in which the input is a single path given in unary: in this case we end up to the open (is it still open? :-) question $P=^?NP$ (through TALLY).

You could change your question to "Are there natural hard problems on caterpillars?", but like in many other contexts the word natural (probably) cannot be defined formally.

As a trivial (fairly natural :-) example of NP-hard problem: "Given a caterpillar $n_1,n_2,...,n_{3m}$ of length $3m$, can it be rearranged into a new caterpillar $n_{j_1}, n_{j_2}, ..., n_{j_{3m}}$ such that all groups of consecutive 3 central nodes (starting from the first) has the same number of total neighbours? ($n_{j_1} + n_{j_2} + n_{j_3} = n_{j_4} + n_{j_5} + n_{j_6} = ...$ and so on)