# 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

• Catepillars can model paths and stars and there are several problems that are NP-Hard on paths or stars. One just has to think a bit to generalize the reductions. – Chandra Chekuri Jan 12 '19 at 15:20
• @ChandraChekuri, this indeed is the direction I am looking for. But most (if not all) natural NP-hard problems on paths or stars take at least one more input such as an integer (as in bandwidth), a weight function on edges, and so on. – Cyriac Antony Jan 14 '19 at 4:01
• Have a look at bandwidth minimization. – Juho Jan 15 '19 at 12:41
• @Juho, The decision version of bandwidth minimization is NP-complete for subcubic caterpillars (see [Burkhard Monien, 1986]); but the problem also takes a +ve integer $k$ as input (along with the caterpillar) – Cyriac Antony Jan 16 '19 at 9:21

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)

• "Are there natural hard problems on caterpillars?", but like in many other contexts the word natural cannot be defined formally. Yeah, true :( – Cyriac Antony Jan 14 '19 at 3:57

(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?

• This doesn't quite work. Just given a caterpillar, you won't know automatically whether any particular vertex is a backbone vertex or a leg vertex. Nor will you know which side of the backbone is the "start" and which is the "end". Obviously you can deduce some of this info (i.e. a vertex of degree not equal to 1 must be a backbone vertex). However, your solution can be easily modified to adjust for this. For example, attach 2 legs instead of one in the $b_i = 1$ case and encode the bit string as a palindrome (with redundant bits). – Mikhail Rudoy Jan 11 '19 at 12:54