1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – codeing_monkey
    Commented Feb 14 at 16:46
  • $\begingroup$ @codeing_monkey Thank you. I will write it though I think it has many words. $\endgroup$
    – licheng
    Commented Feb 15 at 0:35

1 Answer 1

Reset to default
2
$\begingroup$

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}\}\}$.

enter image description here

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.

I think the paper states that there is a polynomial-time algorithm to find them if you make additionnal hypotheses on the graph (though I agree that many details are missing).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I agree. But, I am surprised that the authors claim their polynomial algorithm (to check whether a graph contains no two non-adjacent cycles (and more generally no k non-adjacent cycles)) follows from the fact that these graphs have a polynomial number of induced paths. In fact, before checking, we don't know how many induced paths a given graph has. Note: The testing graph given is general. $\endgroup$
    – licheng
    Commented Feb 15 at 17:34
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Commented Feb 15 at 17:38
  • $\begingroup$ I agree with you. Perhaps we need to determine what c actually is before this algorithm is implemented. I will ask the authors if they have implemented the algorithm. $\endgroup$
    – licheng
    Commented Feb 15 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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