<p>A caterpillar is equivalent to a list of integers <span class="math-container">$n_1,n_2,...,n_m$</span> (given in unary), in which integer <span class="math-container">$n_i$</span> represents a central node <span class="math-container">$i$</span> and its <span class="math-container">$n_i$</span> neighbours.</p>

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

<p>Clearly this is cheating, but a list of integers can encode everything (e.g. a binary number <span class="math-container">$(0,1,0,0,1,1,0,1)$</span>, 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 <em>path</em> given in unary: in this case we end up to the open (is it still open? :-) question <span class="math-container">$P=^?NP$</span> (through <a href="https://en.wikipedia.org/wiki/Unary_language" rel="nofollow noreferrer">TALLY</a>).</p>

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

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

CC BY-SA 4.0
2019-01-14T03:57:40.040Z
`"Are there natural hard problems on caterpillars?", but like in many other contexts the word natural cannot be defined formally.` Yeah, true :(
Cyriac Antony
CC BY-SA 4.0
2019-01-11T20:12:58.263Z
2019-01-16T09:40:10.070Z
2019-01-16T09:40:10.070Z
Marzio De Biasi
<p>(1) Note that any instance <span class="math-container">$G=(V,E)$</span> of the (NP-complete) Hamiltonian cycle problem can be represented by a bit string <span class="math-container">$b_1b_2\cdots b_k$</span>: Just write down the <span class="math-container">$n\times n$</span> adjacency matrix of <span class="math-container">$G$</span> row by row, and merge the rows into one long bit string of length <span class="math-container">$k=n^2$</span>.</p>

<p>(2) Note that you may encode an arbitrary bit string <span class="math-container">$b_1b_2\cdots b_k$</span> into a caterpillar:</p>

<ul>
<li>The backbone of the caterpillar is a path on <span class="math-container">$k+1$</span> vertices <span class="math-container">$v_0,v_1,\ldots,v_k$</span>.</li>
<li>If <span class="math-container">$b_i=0$</span>, then vertex <span class="math-container">$v_i$</span> has zero legs attached to it.</li>
<li>If <span class="math-container">$b_i=1$</span>, then vertex <span class="math-container">$v_i$</span> has one leg attached to it.</li>
<li>Vertex <span class="math-container">$v_0$</span> 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.)</li>
</ul>

<p>(3) Then for instance the following problem is NP-complete:  </p>

<blockquote>
  <p><strong>Instance:</strong> a caterpillar <span class="math-container">$T$</span><br>
  <strong>Question:</strong> does the caterpillar <span class="math-container">$T$</span> encode a bit string <span class="math-container">$b_1b_2\cdots b_k$</span> with <span class="math-container">$k=n^2$</span> so that the corresponding <span class="math-container">$n$</span>-vertex graph <span class="math-container">$G$</span> has a Hamiltonian cycle?</p>
</blockquote>

CC BY-SA 4.0
2019-01-11T12:54:06.623Z
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
CC BY-SA 4.0
2019-01-11T11:34:17.437Z
2019-01-11T11:34:17.437Z
Gamow
<p>My question is <strong>whether there exist an NP-hard problem that has only a caterpillar as input</strong>.</p>

<p>By saying <em>only caterpillar as input</em>, 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.</p>

<p>Instance: a caterpillar <span class="math-container">$T$</span><br>
Question: __________</p>

<p>There are two similar question in the site: <a href="https://cstheory.stackexchange.com/q/1215/47855">NP-hard problems on trees</a>, <a href="https://cstheory.stackexchange.com/q/20861/47855">NP-hard problems on paths</a>. 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.</p>

<p>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?).</p>

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

<p>Thank you</p>

CC BY-SA 4.0
2019-01-12T15:20:37.420Z
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
CC BY-SA 4.0
2019-01-14T04:01:02.960Z
@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
CC BY-SA 4.0
2019-01-15T12:41:22.907Z
Have a look at bandwidth minimization.
Juho
CC BY-SA 4.0
2019-01-16T09:21:53.083Z
@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
<np-hardness><np-complete>
NP-hard problems on the class of caterpillars
Cyriac Antony
# NP-hard problems on the class of caterpillars

(Asked by: username_0 on 2019-01-11)

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](https://cstheory.stackexchange.com/q/1215/47855), [NP-hard problems on paths](https://cstheory.stackexchange.com/q/20861/47855). 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

**Tags:** np-hardness, np-complete
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: Have a look at bandwidth minimization.  
> **username_0**: @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)  

---

## 2 answers

### Answer by username_3 on 2019-01-11. Score: 2

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](https://en.wikipedia.org/wiki/Unary_language)).

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)

> **Comments:**
> **username_0**: `"Are there natural hard problems on caterpillars?", but like in many other contexts the word natural cannot be defined formally.` Yeah, true :(  

---

### Answer by username_4 on 2019-01-11. Score: 1

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

> **Comments:**
> **username_5**: 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).  

---

