Induced path
Encyclopedia
In the mathematical
area of graph theory
, an induced path in an undirected graph G is a path
that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box
problem.
Similarly, an induced cycle is a cycle
that is an induced subgraph of 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 of 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. The induced path number of a graph G is the smallest number of induced paths into which the vertices of the graph may be partitioned, and the closely related path cover number of G is the smallest number of induced paths that together include all vertices of G. The 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.
problem, and it has been studied extensively due to its applications in coding theory and engineering.
. However, this problem can be solved in polynomial time for certain graph families, such as asteroidal-triple-free graphs or graphs with no long holes.
It is also NP-complete to determine whether the vertices of a graph can be partitioned into two induced paths, or two induced cycles. 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
s in graphs, by the following reduction. From any graph G with n vertices, form another graph H with twice as many vertices as G, by adding to G n(n − 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 2k, 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 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(n1/2-ε) 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+m2)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an induced path in an undirected graph G is a path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box
Snake-in-the-box
The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of...
problem.
Similarly, an induced cycle is a cycle
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
that is an induced subgraph of 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 of 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. The induced path number of a graph G is the smallest number of induced paths into which the vertices of the graph may be partitioned, and the closely related path cover number of G is the smallest number of induced paths that together include all vertices of G. The 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
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 , is known as the snake-in-the-boxSnake-in-the-box
The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of...
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 graphComplete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s, and the connected graphs with no induced cycle are the treeTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
s. - A triangle-free graphTriangle-free graphIn the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
is a graph with no induced cycle of length three. - The cographCographIn graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s are exactly the graphs with no induced path of length three. - The chordal graphChordal graphIn the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
s are the graphs with no induced cycle of length four or more. - The even-hole-free graphEven-hole-free graphIn the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices. demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.-Recognition:...
s are the graphs in containing no induced cycles with an even number of vertices. - The trivially perfect graphs 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 graphPerfect graphIn graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
s are the graphs with no odd hole and no odd antihole. - The distance-hereditary graphDistance-hereditary graphIn graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original 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 graphBlock graphIn graph theory, a branch of combinatorial mathematics, a block graph is a type of undirected graph in which every biconnected component is a clique...
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. credit this result to an unpublished communication of Mihalis YannakakisMihalis Yannakakis
Mihalis Yannakakis is a Professor of Computer Science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.-Education and career:...
. However, this problem can be solved in polynomial time for certain graph families, such as asteroidal-triple-free graphs or graphs with no long holes.
It is also NP-complete to determine whether the vertices of a graph can be partitioned into two induced paths, or two induced cycles. 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
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
s in graphs, by the following reduction. From any graph G with n vertices, form another graph H with twice as many vertices as G, by adding to G n(n − 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 2k, 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 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(n1/2-ε) 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+m2)