0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jan 12 at 15:20
  • $\begingroup$ @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. $\endgroup$ – Cyriac Antony 2 days ago
  • $\begingroup$ Have a look at bandwidth minimization. $\endgroup$ – Juho yesterday
  • $\begingroup$ @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) $\endgroup$ – Cyriac Antony 11 hours ago
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ "Are there natural hard problems on caterpillars?", but like in many other contexts the word natural cannot be defined formally. Yeah, true :( $\endgroup$ – Cyriac Antony 2 days ago
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Mikhail Rudoy Jan 11 at 12:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.