NP-hard problems on the class of caterpillars

Question

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

Answer 1

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)

Answer 2

(1) Note that any instance $G=(V,E)$ of the (NP-complete) Hamiltonian cycle problem can be represented by a bit string $b_1b_2\cdots b_k$: Just write down the $n\times n$ adjacency matrix of $G$ row by row, and merge the rows into one long bit string of length $k=n^2$.

(2) Note that you may encode an arbitrary bit string $b_1b_2\cdots b_k$ into a caterpillar:

• The backbone of the caterpillar is a path on $k+1$ vertices $v_0,v_1,\ldots,v_k$.
• If $b_i=0$, then vertex $v_i$ has zero legs attached to it.
• If $b_i=1$, then vertex $v_i$ has one leg attached to it.
• Vertex $v_0$ has three legs attached to it. (This is just a marker to indicate which end of the backbone does encode the beginning of the string.)

(3) Then for instance the following problem is NP-complete:

Instance: a caterpillar $T$
Question: does the caterpillar $T$ encode a bit string $b_1b_2\cdots b_k$ with $k=n^2$ so that the corresponding $n$-vertex graph $G$ has a Hamiltonian cycle?