View source for Induced path

{{short description|Graph path which is an induced subgraph}}
{{Use dmy dates|date=August 2020|cs1-dates=y}}
[[Image:Snake in the box.svg|thumb|An induced path of length four in a [[hypercube graph|cube]]. Finding the longest induced path in a hypercube is known as the [[snake-in-the-box]] problem.]]

In the [[mathematics|mathematical]] area of [[graph theory]], an '''induced path''' in an [[undirected graph]] {{mvar|G}} is a [[path (graph theory)|path]] that is an [[induced subgraph]] of {{mvar|G}}. That is, it is a sequence of [[Vertex (graph theory)|vertices]] in {{mvar|G}} such that each two adjacent vertices in the sequence are connected by an edge in {{mvar|G}}, and each two nonadjacent vertices in the sequence are not connected by any edge in {{mvar|G}}.  An induced path is sometimes called a '''snake''', and the problem of finding long induced paths in [[hypercube graph]]s is known as the [[snake-in-the-box]] problem.

Similarly, an '''induced cycle''' is a [[cycle graph|cycle]] that is an induced subgraph of {{mvar|G}}; induced cycles are also called '''chordless cycles''' or (when the length of the cycle is four or more) '''holes'''. An '''antihole''' is a hole in the [[complement (graph theory)|complement]] of {{mvar|G}}, i.e., an antihole is a complement of a hole.

The length of the longest induced path in a graph has sometimes been called the '''detour number''' of the graph;<ref>{{harvtxt|Buckley|Harary|1988}}.</ref> for [[sparse graph]]s, having bounded detour number is equivalent to having bounded [[tree-depth]].<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Proposition 6.4, p. 122.</ref> The '''induced path number''' of a graph {{mvar|G}} is the smallest number of induced paths into which the vertices of the graph may be partitioned,<ref>{{harvtxt|Chartrand|McCanna|Sherwani|Hossain|1994}}.</ref> and the closely related '''path cover number''' of {{mvar|G}} is the smallest number of induced paths that together include all vertices of {{mvar|G}}.<ref>{{harvtxt|Barioli|Fallat|Hogben|2004}}.</ref> The [[girth (graph theory)|girth]] of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the '''odd girth''' of a graph is also the length of its shortest odd induced cycle.

== Example ==

{{snakes_and_coils_in_the_box.svg}}
The illustration shows a cube, a graph with eight vertices and twelve edges, and an induced path of length four in this graph. A straightforward case analysis shows that there can be no longer induced path in the cube, although it has an induced cycle of length six. The problem of finding the longest induced path or cycle in a hypercube, first posed by {{harvtxt|Kautz|1958}}, is known as the [[snake-in-the-box]] problem, and it has been studied extensively due to its applications in coding theory and engineering.

== Characterization of graph families ==

Many important graph families can be characterized in terms of the induced paths or cycles of the graphs in the family.

* Trivially, the connected graphs with no induced path of length two are the [[complete graph]]s, and the connected graphs with no induced cycle are the [[tree (graph theory)|tree]]s.
* A [[triangle-free graph]] is a graph with no induced cycle of length three.
* The [[cograph]]s are exactly the graphs with no induced path of length three.
* The [[chordal graph]]s are the graphs with no induced cycle of length four or more.
* The [[even-hole-free graph]]s are the graphs containing no induced cycles with an even number of vertices.
* The [[trivially perfect graph]]s are the graphs that have neither an induced path of length three nor an induced cycle of length four.
* By the strong perfect graph theorem, the [[perfect graph]]s are the graphs with no odd hole and no odd antihole.
* The [[distance-hereditary graph]]s are the graphs in which every induced path is a shortest path, and the graphs in which every two induced paths between the same two vertices have the same length.
* The [[block graph]]s are the graphs in which there is at most one induced path between any two vertices, and the connected block graphs are the graphs in which there is exactly one induced path between every two vertices.

== Algorithms and complexity ==
It is NP-complete to determine, for a graph ''G'' and parameter ''k'', whether the graph has an induced path of length at least ''k''. {{harvtxt|Garey|Johnson|1979}} credit this result to an unpublished communication of [[Mihalis Yannakakis]]. However, this problem can be solved in polynomial time for certain graph families, such as asteroidal-triple-free graphs<ref>{{harvtxt|Kratsch|Müller|Todinca|2003}}.</ref> or graphs with no long holes.<ref>{{harvtxt|Gavril|2002}}.</ref>

It is also NP-complete to determine whether the vertices of a graph can be partitioned into two induced paths, or two induced cycles.<ref>{{harvtxt|Le|Le|Müller|2003}}.</ref> As a consequence, determining the induced path number of a graph is NP-hard.

The complexity of approximating the longest induced path or cycle problems can be related to that of finding large [[Independent set (graph theory)|independent set]]s in graphs, by the following reduction.<ref>{{harvtxt|Berman|Schnitger|1992}}.</ref> From any graph ''G'' with ''n'' vertices, form another graph ''H'' with twice as many vertices as ''G'', by adding to ''G'' ''n''(''n''&nbsp;&minus;&nbsp;1)/2 vertices having two neighbors each, one for each pair of vertices in ''G''. Then if ''G'' has an independent set of size ''k'', ''H'' must have an induced path and an induced cycle of length 2''k'', formed by alternating vertices of the independent set in ''G'' with vertices of ''I''.  Conversely, if ''H'' has an induced path or cycle of length ''k'', any maximal set of nonadjacent vertices in ''G'' from this path or cycle forms an independent set in ''G'' of size at least ''k''/3. Thus, the size of the maximum independent set in ''G'' is within a constant factor of the size of the longest induced path and the longest induced cycle in ''H''. Therefore, by the results of {{harvtxt|Håstad|1996}} on inapproximability of independent sets, unless NP=ZPP, there does not exist a polynomial time algorithm for approximating the longest induced path or the longest induced cycle to within a factor of O(''n''<sup>1/2-ε</sup>) of the optimal solution.

Holes (and antiholes in graphs without chordless cycles of length 5) in a graph with n vertices and m edges may be detected in time (n+m<sup>2</sup>).<ref>{{harvtxt|Nikolopoulos|Palios|2004}}.</ref>

==Atomic cycles==
Atomic cycles are a generalization of chordless cycles, that contain no ''n''-chords. Given some cycle, an ''n''-chord is defined as a path of length ''n'' connecting two points on the cycle, where ''n'' is less than the length of the shortest path on the cycle connecting those points. If a cycle has no ''n''-chords, it is called an atomic cycle, because it cannot be decomposed into smaller cycles.<ref>{{harvtxt|Gashler|Martinez|2012}}.</ref>
In the worst case, the atomic cycles in a graph can be enumerated in O(''m''<sup>2</sup>) time, where ''m'' is the number of edges in the graph.

==Notes==
{{reflist}}

==References==
{{refbegin}}
*{{cite journal
 | last1 = Barioli | first1 = Francesco
 | last2 = Fallat | first2 = Shaun
 | last3 = Hogben | first3 = Leslie | author-link3 = Leslie Hogben
 | title = Computation of minimal rank and path cover number for certain graphs
 | url = http://orion.math.iastate.edu/lhogben/research/BFHmrank.pdf
 | doi = 10.1016/j.laa.2004.06.019
 | journal = [[Linear Algebra and Its Applications]]
 | volume = 392
 | date = 2004
 | pages = 289–303| doi-access = free
 }}
*{{cite journal
 | last1 = Berman | first1 = Piotr
 | last2 = Schnitger | first2 = Georg
 | title = On the complexity of approximating the independent set problem
 | journal = [[Information and Computation]]
 | volume = 96
 | issue = 1
 | date = 1992
 | pages = 77–94
 | doi = 10.1016/0890-5401(92)90056-L
 | doi-access = free}}  
*{{cite journal
 | last1 = Buckley | first1 = Fred
 | last2 = Harary | first2 = Frank | author-link2 = Frank Harary
 | title = On longest induced paths in graphs
 | journal = Chinese Quarterly Journal of Mathematics
 | volume = 3
 | date = 1988
 | issue = 3
 | pages = 61–65}}
*{{cite journal
 | last1 = Chartrand | first1 = Gary | author-link1 = Gary Theodore Chartrand
 | last2 = McCanna | first2 = Joseph
 | last3 = Sherwani | first3 = Naveed
 | last4 = Hossain | first4 = Moazzem
 | last5 = Hashmi | first5 = Jahangir
 | title = The induced path number of bipartite graphs
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | volume = 37
 | date = 1994
 | pages = 191–208}}
*{{cite book
 | last1 = Garey | first1 = Michael R. | author-link1 = Michael Garey
 | last2 = Johnson | first2 = David S. | author-link2 = David S. Johnson
 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness.
 | url = https://archive.org/details/computersintract0000gare
 | url-access = registration
 | date = 1979
 | publisher = [[W. H. Freeman]]
 | page = [https://archive.org/details/computersintract0000gare/page/196 196]}}
*{{cite journal 
 |first1 = Michael |last1 = Gashler
 |first2 = Tony |last2 = Martinez
 |title = Robust manifold learning with CycleCut
 |url = http://axon.cs.byu.edu/papers/cyclecut.pdf
 |journal = Connection Science
 |volume = 24
 |number = 1
 |pages = 57–69
 |date = 2012
 |doi = 10.1080/09540091.2012.664122}}
*{{cite journal
 | last = Gavril | first = Fănică
 | title = Algorithms for maximum weight induced paths
 | journal = [[Information Processing Letters]]
 | doi = 10.1016/S0020-0190(01)00222-8
 | volume = 81
 | issue = 4
 | date = 2002
 | pages = 203–208}} 	
*{{cite conference
 | last = Håstad | first = Johan | author-link = Johan Håstad
 | title = Clique is hard to approximate within ''n''<sup>1−ε</sup>
 | book-title = Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science
 | url = http://www.nada.kth.se/~johanh/cliqueinap.ps
 | doi = 10.1109/SFCS.1996.548522
 | pages = 627–636
 | date = 1996}}
*{{cite journal
 | last = Kautz | first = William H.
 | author-link = William H. Kautz
 | title = Unit-distance error-checking codes
 | journal = [[IRE Transactions on Electronic Computers]]
 | volume = EC-7
 | issue = 2
 | pages = 179–180
 | date = June 1958
 | doi = 10.1109/TEC.1958.5222529
 | s2cid=26649532}}
*{{cite conference
 |last1       = Kratsch
 |first1      = Dieter
 |last2       = Müller
 |first2      = Haiko
 |last3       = Todinca
 |first3      = Ioan
 |title       = Feedback vertex set and longest induced path on AT-free graphs
 |book-title  = Graph-theoretic concepts in computer science
 |pages       = 309–321
 |publisher   = Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag
 |location    = Berlin
 |url         = http://lita.sciences.univ-metz.fr/~kratsch/publications/KMT_preprocWG.ps
 |doi         = 10.1007/b93953
 |date        = 2003
 |url-status  = dead
 |archive-url = https://web.archive.org/web/20061125133622/http://lita.sciences.univ-metz.fr/~kratsch/publications/KMT_preprocWG.ps
 |archive-date = 2006-11-25
}}
*{{cite journal
 | last1 = Le | first1 = Hoàng-Oanh
 | last2 = Le | first2 = Van Bang
 | last3 = Müller | first3 = Haiko
 | title = Splitting a graph into disjoint induced paths or cycles
 | series = The Second International Colloquium "Journées de l'Informatique Messine", Metz, 2000
 | journal = [[Discrete Applied Mathematics]]
 | volume = 131
 | date = 2003
 | issue = 1
 | pages = 199–212
 | doi = 10.1016/S0166-218X(02)00425-0
 | url = http://www.informatik.uni-rostock.de/~le/Research/splitting.pdf
 | archive-url = https://web.archive.org/web/20160303174028/http://www.informatik.uni-rostock.de/~le/Research/splitting.pdf
 | archive-date = 2016-03-03| doi-access = free
 }}
*{{cite book
 | last1 = Nešetřil | first1 = Jaroslav | author-link1 = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | author-link2 = Patrice Ossona de Mendez
 | chapter = Chapter 6. Bounded height trees and tree-depth
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | location = Heidelberg
 | mr = 2920058
 | pages = 115–144
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | date = 2012}}
*{{Cite conference
 | first1 = Stavros D. | last1 = Nikolopoulos | first2 = Leonidas | last2 = Palios
 | contribution = Hole and antihole detection in graphs
 | title = Hole and antihole detection in graphs
 | book-title = Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms
 | date = 2004
 | pages = 850–859
 | url = http://portal.acm.org/citation.cfm?id=982792.982920}}
{{refend}}

[[Category:Graph theory objects]]