0

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

Cyriac Antony
  • 1,723
  • 9
  • 21
  • 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. – 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 04: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 09:21

2 Answers2

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).

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)

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • "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 03:57
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?

Gamow
  • 5,772
  • 6
  • 25
  • 39
  • 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