# Find all the induced paths with a start vertex

Let $$G$$ be a graph and let $$v$$ be a vertex. Is there a polynomial algorithm for the following operation?

Operation. Find all the induced paths in $$G$$ with first vertex $$v$$.

Background

This problem is the confusion I encountered while reading the article Induced paths in graphs without anticomplete cycles. The authors asserted that there is a polynomial algorithm to check whether a graph contains no two non-adjacent cycles (and more generally no k non-adjacent cycles). Their algorithm is as follows:

• For each vertex $$v$$, find all the induced paths with first vertex $$v$$.
• For each induced path $$P$$, find all induced cycles that consist of $$P$$ and one extra vertex.
• Check whether any two of these cycles are disjoint and have no edges between them.

I am puzzled by the first step. If that's the case, then I think that finding the longest induced path in a graph would be possible with a polynomial algorithm. But as far as I know, it is NP-hard. See https://en.wikipedia.org/wiki/Induced_path

• I think it is best to provide some background information on the problem and write down some of your thoughts. After all, the purpose of CS SE is to built a repository of meaningful information for future members. Feb 14 at 16:46
• @codeing_monkey Thank you. I will write it though I think it has many words. Feb 15 at 0:35

Consider the following graph $$G = (V, E)$$ where:
• $$V = \{v_0\}\cup \{u_1,…, u_n\}\cup \{v_1, …, v_n\}$$;
• $$E = \{\{v_0,u_1\}, \{v_0, v_1\}\}\cup \bigcup\limits_{k=1}^{n-1}\{\{u_k, u_{k+1}\}, \{u_k, v_{k+1}\}, \{v_k, u_{k+1}\}, \{v_k, v_{k+1}\}\}$$.
Then the graph has more than $$2^n$$ induced paths from $$v_0$$. So there is no way to find all of them in polynomial time.
• Well that could still be true: you could enumerate all induced paths, and answer false when the number of induced paths becomes greater than $|G|^c$. However I am not an expert on the question. Perhaps you could contact the authors to ask further questions? Feb 15 at 17:38