Induced path

Induced path
An induced path of length four in a cube. Finding the longest induced path in a hypercube is known as the snake-in-the-box problem.

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.[1] 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,[2] and the closely related path cover number of G is the smallest number of induced paths that together include all vertices of G.[3] 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.

Contents

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 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 graphs, and the connected graphs with no induced cycle are the trees.
  • A triangle-free graph is a graph with no induced cycle of length three.
  • The cographs are exactly the graphs with no induced path of length three.
  • The chordal graphs are the graphs with no induced cycle of length four or more.
  • The even-hole-free graphs 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 graphs are the graphs with no odd hole and no odd antihole.
  • The distance-hereditary graphs 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 graphs 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. 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[4] or graphs with no long holes.[5]

It is also NP-complete to determine whether the vertices of a graph can be partitioned into two induced paths, or two induced cycles.[6] 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 sets in graphs, by the following reduction.[7] 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 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(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)[8]

Notes

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • 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. The first vertex is called the start vertex and the last vertex is called the end vertex . Both… …   Wikipedia

  • Induced subgraph isomorphism problem — In complexity theory and graph theory, induced subgraph isomorphism is an NP complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.Formally, the problem takes as input two graphs G 1=( V 1, E 1)… …   Wikipedia

  • Hamiltonian path — This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem. A Hamiltonian cycle in a dodecahedron …   Wikipedia

  • Geomagnetically induced current — Geomagnetically induced currents (GIC), affecting the normal operation of long technological conductor systems, are a manifestation at ground level of space weather. During space weather events (or geomagnetic storms) Earth s near space current… …   Wikipedia

  • pilot-induced oscillation — An undulating flight path brought about by the pilot’s overcontrolling the aircraft. Every subsequent departure is bigger than the previous one if the pilot’s correction is out of phase …   Aviation dictionary

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”