Exploring fully-leafed induced subcaterpillars?

[ablondin]

@enadeau : When studying the induced subtrees of a general graph, it could be interesting to restrict our attention only to subcaterpillars:

• The problem in itself is interesting;
• This would reduce significantly the space explored by the algorithm, so that we might expect results for larger graphs;
• This could potentially lead to a lower bound for the leaf function. In other words, it might provide an estimate of the leaf function for large graphs.

Do you think it would be hard to extend the current code so that it supports this new feature?

[enadeau]

@ablondin: Humm, I think it's possible but not trivial. The two main issues that I see are:

• The data structure needs to be adapted, I don't see how to use it directly to iterate on subcaterpillar instead of subtree (I need to put some time to think about that)
• I'm not sure if the potential function is still useful in this context. Maybe we will need a new one.

Otherwise I agree that it worth more exploration. Did you think that the decision version similar to LIS is NP-complete? (that would be an interesting question too)