Computational complexity theory
From Wikipedia, the free encyclopedia
Jump to: navigation, search
In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. This cost is usually measured in terms of abstract parameters such as time and space, called computational resources. Time represents the number of steps it takes to solve a problem and space represents the quantity of information storage required or how much memory it takes. There are often tradeoffs between time and space that have to be considered when trying to solve a computational problem. It often turns out that an alternative algorithm will require less time but more space (or vice versa) to solve a given problem. Time requirements sometimes must be amortized to determine the time cost for a well defined average case. Space requirements can be profiled over time, too, especially in consideration of a multi-user computer system.
Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. In this case, "parallelizable time" and "non-parallelizable time" are considered. The latter is important in real-time applications, and it gives a limit to how far the computation can be parallelized. Some steps must be done sequentially because they depend on the results of previous steps.
Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.
Overview
After the theory explaining which problems can be solved and which cannot be, it was natural to ask about the relative computational difficulty of computable functions. This is the subject matter of computational complexity.
A single "problem" is an entire set of related questions, where each question is a finite-length string. For example, the problem FACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem.
The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in n² steps. In this example we say the problem has a time complexity of n². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use Big O notation. If a problem has time complexity O(n²) on one typical computer, then it will also have complexity O(n²p(n)) on most other computers for some polynomial p(n), so this notation allows us to generalize away from the details of a particular computer.
Example: Mowing grass has linear complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic complexity because a double sized dictionary only has to be opened one time more (e.g. exactly in the middle - then the problem is reduced to the half).
[edit]
Decision problems
Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always YES/NO. For example, the problem IS-PRIME is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a language, which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES.
Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, the problem HAS-FACTOR is: given integers n and k written in binary, return whether n has any prime factors less than k. If we can solve HAS-FACTOR with a certain amount of resources, then we can use that solution to solve FACTORIZE without much more resources. Just do a binary search on k until you find the smallest factor of n. Then divide out that factor, and repeat until you find all the factors.
Complexity theory often makes a distinction between YES answers and NO answers. For example, the set NP is defined as the set of problems where the YES instances can be checked "quickly" (i.e. in polynomial time). The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The complement of a problem is one where all the YES and NO answers are swapped, such as IS-COMPOSITE for IS-PRIME.
An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is determined by the time hierarchy theorem. A similar space hierarchy theorem can also be derived.
[edit]
Computational resources
Complexity theory analyzes the difficulty of computational problems in terms of many different computational resources. The same problem can be described in terms of the necessary amounts of many different computational resources, including time, space, randomness, alternation, and other less-intuitive measures. A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.
Perhaps the most well-studied computational resources are deterministic time (DTIME) and deterministic space (DSPACE). These resources represent the amount of computation time and memory space needed on a deterministic computer, like the computers that actually exist. These resources are of great practical interest, and are well-studied.
Some computational problems are easier to analyze in terms of more unusual resources. For example, a nondeterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that nondeterministic time is a very important resource in analyzing computational problems.
Many more unusual computational resources have been used in complexity theory. Technically, any complexity measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum complexity axioms.
[edit]
Complexity classes
A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.
The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases.
The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, the Hamiltonian path problem and the Vertex cover problem. All the problems in this class have the property that their solutions can be checked effectively.
Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.
[edit]
The P = NP question
The question of whether P is the same set as NP is the most important open question in theoretical computer science. There is even a $1,000,000 prize for solving it. (See complexity classes P and NP and oracles).
Questions like this motivate the concepts of hard and complete. A set of problems X is hard for a set of problems Y if every problem in Y can be transformed easily into some problem in X with the same answer. The definition of "easily" is different in different contexts. The most important hard set is NP-hard. Set X is complete for Y if it is hard for Y, and is also a subset of Y. The most important complete set is NP-complete. See the articles on those two sets for more detail on the definition of "hard" and "complete".
[edit]
Intractability
Problems that are solvable in theory, but can't be solved in practice, are called intractable. What can be solved "in practice" is open to debate, but in general only problems that have polynomial-time solutions are solvable for more than the smallest inputs. Problems that are known to be intractable include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable.
To see why exponential-time solutions are not usable in practice, consider a problem that requires 2n operations to solve (n is the size of the input). For a relatively small input size of n=100, and assuming a computer that can perform 1010 (10 giga) operations per second, a solution would take about 4*1012 years, much longer than the current age of the universe.
[edit]

Your continued donations keep Wikipedia running!    
Glossary of graph theory
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage.
Contents
•	1 Basics 
o	1.1 Subgraphs 
o	1.2 Walks 
o	1.3 Trees 
o	1.4 Cliques 
o	1.5 Strongly connected component 
o	1.6 Knots 
o	1.7 Minors 
o	1.8 Embedding 
•	2 Adjacency and degree 
o	2.1 Independence 
•	3 Connectivity 
•	4 Distance 
•	5 Genus 
•	6 Weighted graphs and networks 
•	7 Direction 
•	8 Various 
•	9 To be merged 
•	10 See also 
•	11 References 	
[edit]
Basics
A graph G consists of two types of elements, namely vertices and edges. Every edge has two endpoints in the set of vertices, and is said to connect or join the two endpoints. The set of edges can thus be defined as a subset of the family of all two-element sets of vertices. Often, however, the set of vertices is considered as a set, and there is an incidence relation which maps each edge to the pair of vertices that are its endpoints.
Edges may be endowed with direction, leading to the notion of a directed graph or a digraph, see Section Direction.
Alternative models of graph exist; e.g., a graph may be thought as a Boolean binary function over the set of vertices or as a square (0,1)-matrix.
A vertex (basic element) is simply drawn as a node or a dot. The vertex set of G is usually denoted by V(G), or V when there is no danger of confusion. The order of a graph is the number of its vertices, i.e. |V(G)|.
An edge (a set of two elements) is drawn as a line connecting two vertices, called endvertices, or endpoints. An edge with endvertices x and y is denoted by xy without any symbol in between, so, do not write x⋅y. The edge set of G is usually denoted by E(G), or E when there is no danger of confusion.
The size of a graph is the number of its edges, i.e. |E(G)|.
A loop is an edge whose endvertices are the same vertex. A link has two distinct endvertices. An edge is multiple if there is another edge with the same endvertices; otherwise it is simple. The multiplicity of an edge is the number of multiple edges sharing the same endvertices; the multiplicity of a graph, the maximum multiplicity of its edges. A graph is a simple graph if it has no multiple edges or loops, a multigraph if it has multiple edges, but no loops, and a multigraph or pseudograph if it contains both multiple edges and loops (the literature is highly inconsistent). When stated without any qualification, a graph is almost always assumed to be simple—or one has to judge from the context.
Graph labeling usually refers to the assignment of unique labels (usually natural numbers) to the edges and vertices of a graph. Graphs with labeled edges or vertices are known as labeled, those without as unlabeled. More specifically, graphs with labeled vertices only are vertex-labeled, those with labeled edges only are edge-labeled. (This usage is to distinguish between graphs with identifiable vertex or edge sets on the one hand, and isomorphism types or classes of graphs on the other.)

A labelled simple graph with vertex set V = {1, 2, 3, 4, 5, 6} and edge set E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (with the map w being the identity).
A hyperedge is an edge that is allowed to take on any number of vertices, possibly more than 2. A graph that allows any hyperedge is called a hypergraph. A simple graph can be considered a special case of the hypergraph, namely the 2-uniform hypergraph. However, when stated without any qualification, an edge is always assumed to consist of at most 2 vertices, and a graph is never confused with a hypergraph.
An anti-edge is an edge that "is not there". More formally, for two vertices u and v, {u,v} is an anti-edge in a graph G if (u,v) is not an edge in G. This means that there is either no edge between the two vertices or there is only an edge (v,u) from v to u if G is directed.
An anti-triangle is a set of three vertices none of which are connected.
The complement of a graph G is a graph with the same vertex set as G but with an edge set such that xy is an edge in if and only if xy is not an edge in G.
An edgeless graph or empty graph is a graph possibly with some vertices, but no edges. Or, it is a graph with no vertices and no edges.
The null graph is the graph with no vertices and no edges. Or, it is a graph with no edges and any number n of vertices, in which case it may be called the null graph on n vertices. (There is no consistency at all in the literature.)
A graph is infinite if it has infinitely many vertices or edges or both; otherwise the graph is finite. An infinite graph where every vertex has finite degree is called locally finite. When stated without any qualification, a graph is usually assumed to be finite.
Two graphs G and H are said to be isomorphic, denoted by G ~ H, if there is a one-to-one correspondence, called an isomorphism, between the vertices of the graph such that two vertices are adjacent in G if and only if their corresponding vertices are adjacent in H. Likewise, a graph G is said to be homomorphic to a graph H if there is a mapping, called a homomorphism, from V(G) to V(H) such that if two vertices are adjacent in G then their corresponding vertices are adjacent in H.
[edit]
Subgraphs
A subgraph of a graph G is a graph whose vertex and edge sets are subsets of those of G. In the other direction, a supergraph of a graph G is a graph that contains G as a subgraph. We say a graph G contains another graph H if some subgraph of G is H or is isomorphic to H (depending on the needs of the situation).
A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G. We say H spans G.
A subgraph H of a graph G is said to be induced if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has the most edges that appear in G over the same vertex set. If H is chosen based on a vertex subset S of V(G), then H can be written as G[S] and is said to be induced by S.
A graph that does not contain H as an induced subgraph is said to be H-free.
A universal graph in a class K of graphs is a simple graph in which every element in K can be embedded as a subgraph.
[edit]
Walks
A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex, in which each vertex is incident to the two edges that precede and follow it in the sequence, and the vertices that precede and follow an edge are the endvertices of that edge. A walk is closed if its first and last vertices are the same, and open if they are different.
The length l of a walk is the number of edges that it uses. For an open walk, l = n–1, where n is the number of vertices visited. For a closed walk, l = n (the start/end vertex is listed twice, but is not counted twice). In the example graph, (1, 2, 5, 1, 2, 3) is an open walk with length 5, and (4, 5, 2, 1, 5, 4) is a closed walk of length 5.
A trail is a walk in which all the edges are distinct. A closed trail has been called a tour or circuit, but these are not universal, and the latter is often reserved for a regular subgraph of degree two.
Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually defined to be simple, meaning that every vertex is incident to at most two edges. (The term chain has also been used to refer to a walk in which all vertices (and edges) are distinct.) In the example graph, (5, 2, 1) is a path of length 2. The closed equivalent to this type of walk is called a cycle. Like path, this term traditionally referred to any closed walk, but now is usually understood to be simple by definition. In the example graph, (1, 5, 2, 1) is a cycle of length 3. (A cycle, unlike a path, is not allowed to have length 0.) Paths and cycles of n vertices are often denoted by Pn and Cn, respectively. (Some authors use the length instead of the number of vertices, however.)
A cycle that has odd length is an odd cycle; otherwise it is an even cycle. One theorem is that a graph is bipartite if and only if there does not exist any odd cycle. (See complete bipartite graph.)
The girth of a graph is the length of a shortest (simple) cycle in the graph; and the circumference, the length of a longest (simple) cycle. The girth and circumference of an acyclic graph are defined to be infinity ∞.
A graph is acyclic if it contains no cycles; unicyclic if it contains exactly one cycle; and pancyclic if it contains cycles of every possible length (from 3 to the order of the graph).
C1 is a loop, C2 is a pair of digons (multiple edges), and C3 is called a triangle.
A path or cycle is Hamiltonian (or spanning) if it uses all vertices exactly once. A graph that contains a Hamiltonian path is traceable; and one that contains a Hamiltonian path for any given pair of (distinct) endvertices is a Hamiltonian connected graph. A graph that contains a Hamiltonian cycle is a Hamiltonian graph.
A trail or circuit (or cycle) is Eulerian if it uses all edges precisely once. A graph that contains an Eulerian trail is traversable. A graph that contains an Eulerian circuit is an Eulerian graph.
The example graph does not contain an Eulerian trail, but it does contain a Hamiltonian path.
Two paths are internally disjoint (some people call it independent) if they do not have any vertex in common, except the first and last ones.
A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct endvertices. A theta0 graph has seven vertices which can be arranged as the vertices of a regular hexagon plus an additional vertex in the center. The eight edges are the perimeter of the hexagon plus one diameter.
[edit]
Trees
A tree is a connected acyclic simple graph. A vertex of degree 1 is called a leaf, or pendant vertex. An edge incident to a leaf is an leaf edge, or pendant edge. (Some people define a leaf edge as a leaf and then define a leaf vertex on top of it. These two sets of definitions are often used interchangeably.) A non-leaf vertex is an internal vertex. Sometimes, one vertex of the tree is distinguished, and called the root. A rooted tree is a tree with a root. Rooted trees are often treated as directed acyclic graphs with the edges pointing away from the root.
Trees are commonly used as data structures in computer science (see tree data structure).
A forest is a vertex-disjoint union of trees; or, equivalently, an acyclic graph.
A subtree of the graph G is a subgraph that is a tree.
A spanning tree is a spanning subgraph that is a tree. Every graph has a spanning forest. But only a connected graph has a spanning tree.
A special kind of tree called a star is K1,k. An induced star with 3 edges is a claw.
A k-ary tree is a rooted tree in which every internal vertex has k children. An 1-ary tree is just a path. A 2-ary tree is also called a binary tree.
[edit]
Cliques
The complete graph Kn of order n is a simple graph with n vertices in which every vertex is adjacent to every other. The example graph is not complete. The complete graph on n vertices is often denoted by Kn. It has n(n-1)/2 edges (corresponding to all possible choices of pairs of vertices).
A clique (pronounced "cleek") in a graph is a set of pairwise adjacent vertices. Since any subgraph induced by a clique is a complete subgraph, the two terms and their notations are usually used interchangeably. A k-clique is a clique of order k. In the example graph above, vertices 1, 2 and 5 form a 3-clique, or a triangle.
The clique number ω(G) of a graph G is the order of a largest clique in G.
[edit]
Strongly connected component
A related but weaker concept is that of a strongly connected component. Informally, a strongly connected component of a graph is a subgraph where all nodes in the subgraph are reachable by all other nodes in the subgraph. Reachability between nodes is established by the existence of a path between the nodes.
A directed graph can be decomposed into strongly connected components by running the Depth-first search (DFS) algorithm twice: first, on the graph itself and next on the transpose of the graph in decreasing order of the finishing times of the first DFS. Given a directed graph G, the transpose GT is the graph G with all the edge directions reversed.
[edit]
Knots
A knot in a directed graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot have other vertices in the knot as destinations. Thus it is impossible to leave the knot while following the directions of the edges.
If a general resource graph is expedient, then a knot is a sufficient condition for deadlock.
[edit]
Minors
A minor G2 = (V2,E2) of G1 = (V1,E1) is an injection from V2 to V1 such that every edge in E2 corresponds to a path (disjoint from all other such paths) in G1 such that every vertex in V1 is in one or more paths, or is part of the injection from V1 to V2. This can alternatively be phrased in terms of contractions, which are operations which collapse a path and all vertices on it into a single edge (see edge contraction).
[edit]
Embedding
An embedding G1 = (V1,E1) of G2 = (V2,E2) is an injection from V2 to V1 such that every edge in E2 corresponds to a path (disjoint from all other such paths) in G1.
[edit]
Adjacency and degree
In graph theory, degree, especially that of a vertex, is usually a measure of immediate adjacency.
An edge connects two vertices; these two vertices are said to be incident to that edge, or, equivalently, that edge incident to those two vertices. All degree-related concepts have to do with adjacency or incidence.
The degree, or valency, dG(v) of a vertex v in a graph G is the number of edges incident to v, with loops being counted twice. A vertex of degree 0 is an isolated vertex. A vertex of degree 1 is a leaf. In the example graph vertices 1 and 3 have a degree of 2, vertices 2,4 and 5 have a degree of 3 and vertex 6 has a degree of 1. If E is finite, then the total sum of vertex degrees is equal to twice the number of edges.
A degree sequence is a list of degrees of a graph in non-increasing order (e.g. d1 ≥ d2 ≥ … ≥ dn). A sequence of non-increasing integers is realizable if it is a degree sequence of some graph.
Two vertices u and v are considered adjacent if an edge exists between them. We denote this by u ↓ v. In the above graph, vertices 1 and 2 are adjacent, but vertices 2 and 4 are not. The set of neighbors, called a (open) neighborhood NG(v) for a vertex v in a graph G, consists of all vertices adjacent to v but not including v. When v is also included, it is called a closed neighborhood, denoted by NG[v]. When stated without any qualification, a neighborhood is assumed to be open. The subscript G is usually dropped when there is no danger of confusion. In the example graph, vertex 1 has two neighbors: vertices 2 and 5. For a simple graph, the number of neighbors that a vertex has coincides with its degree.
A dominating set of a graph is a vertex subset whose closed neighborhood includes all vertices of the graph. A vertex v dominates another vertex u if there is an edge from v to u. A vertex subset V dominates another vertex subset U if every vertex in U is adjacent to some vertex in V. The minimum size of a dominating set is the domination number γ(G).
In computers, a finite, directed or undirected graph (with n vertices, say) is often represented by its adjacency matrix: an n-by-n matrix whose entry in row i and column j gives the number of edges from the i-th to the j-th vertex.
Spectral graph theory studies relationships between the properties of the graph and its adjacency matrix.
The maximum degree Δ(G) of a graph G is the largest degree over all vertices; the minimum degree δ(G), the smallest.
A graph in which every vertex has the same degree is regular. It is k-regular if every vertex has degree k. A 0-regular graph is an independent set. A 1-regular graph is a matching. A 2-regular graph is a vertex disjoint union of cycles. A 3-regular graph is said to be cubic, or trivalent.
A k-factor is a k-regular spanning subgraph. An 1-factor is a perfect matching. A partition of edges of a graph into k-factors is called a k-factorization. A k-factorable graph is a graph that admits a k-factorization.
A graph is biregular if it has unequal maximum and minimum degrees and every vertex has one of those two degrees.
A strongly regular graph is a regular graph such that any adjacent vertices have the same number of common neighbors as other adjacent pairs and that any nonadjacent vertices have the same number of common neighbors as other nonadjacent pairs.
[edit]
Independence
In graph theory, the word independent usually carries the connotation of pairwise disjoint or mutually nonadjacent. In this sense, independence is a form of immediate nonadjacency. An isolated vertex is a vertex not incident to any edges. An independent set, or stable set or staset, is a set of isolated vertices. Since the graph induced by any independent set is an empty graph, the two terms are usually used interchangeably. In the example above, vertices 1, 3, and 6 form an independent set; and 3, 5, and 6 form another one.
The independence number α(G) of a graph G is the size of a largest independent set of G.
A graph can be decomposed into independent sets in the sense that the entire vertex set of the graph can be partitioned into pairwise disjoint independent subsets. Such independent subsets are called partite sets, or simply parts.
A graph that can be decomposed into two partite sets but not fewer is bipartite; three sets but not fewer, tripartite; k sets but not fewer, k-partite; and an unknown number of sets, multipartite. An 1-partite graph is the same as an independent set, or an empty graph. A 2-partite graph is the same as a bipartite graph. A graph that can be decomposed into k partite sets is also said to be k-colorable.
A complete multipartite graph is a graph in which vertices are adjacent if and only if they belong to different partite sets. A complete bipartite graph is also referred to as a biclique.
A k-partite graph is semiregular if each of its partite sets has a uniform degree; equipartite if each partite set has the same size; and balanced k-partite if each partite set differs in size by at most 1 with any other.
The matching number α′(G) of a graph G is a the size of a largest matching, or pairwise vertex disjoint edges, of G.
A spanning matching, also called a perfect matching is a matching that covers all vertices of a graph.
[edit]
Connectivity
Connectivity extends the concept of adjacency and is essentially a form (and measure) of concatenated adjacency.
If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be connected; otherwise, the graph is disconnected. A graph is totally disconnected if there is no path connecting any pair of vertices. This is just another name to describe an empty graph or independent set.
A cut vertex, or articulation point, is a vertex whose removal disconnects a graph. A cut set, or vertex cut or separating set, is a set of vertices whose removal disconnects the graph. A bridge is an analogous edge (see below).
If it is always possible to establish a path from any vertex to every other one even after removing any k - 1 vertices, then the graph is said to be k-connected. Note that a graph is k-connected if and only if it contains k internally disjoint paths between any two vertices. The example graph above is connected (and therefore 1-connected), but not 2-connected. The connectivity κ(G) of a graph G is the minimum number of vertices needed to disconnect G. By convention, Kn has connectivity n - 1; and a disconnected graph has connectivity 0.
A bridge, or cut edge or isthmus, is an edge whose removal disconnects a graph. (For example, a tree is made entirely of bridges.) A disconnecting set is a set of edges whose removal increases the number of components. An edge cut is the set of all edges having one endvertex in some proper vertex subset S and another endvertex in V(G)\S. Edges of K3 form a disconnecting set but not an edge cut. Any two edges of K3 form a minimal disconnecting set as well as an edge cut. An edge cut is necessarily a disconnecting set; and a minimal disconnecting set of a nonempty graph is necessarily an edge cut. A bond is a minimal (but not necessarily minimum), nonempty set of edges whose removal disconnects a graph. A cut vertex is an analogous vertex (see above).
A graph is k-edge-connected if any subgraph formed by removing any k - 1 edges is still connected. The edge connectivity κ′(G) of a graph G is the minimum number of edges needed to disconnect G. One well-known result is that κ(G) ≤ κ′(G) ≤ δ(G).
A component is a maximally connected subgraph; a block, either a maximally 2-connected subgraph or a bridge with its endvertices; and a biconnected component, a maximal set of edges in which any two members lie on a common simple cycle.
A separating vertex of a graph is a vertex whose removal from the graph increases its number of connected components. A biconnected component can be defined as a subgraph induced by a maximal set of nodes that has no separating vertex.
[edit]
Distance
The distance dG(u, v) between two (not necessary distinct) vertices u and v in a graph G is the length of a shortest path between them. The subscript G is usually dropped when there is no danger of confusion. When u and v are identical, their distance is 0. When u and v are unreachable from each other, their distance is defined to be infinity ∞.
The eccentricity εG(v) of a vertex v in a graph G is the maximum distance from v to any other vertex. The diameter diam(G) of a graph G is the maximum eccentricity over all vertices in a graph; and the radius rad(G), the minimum. When there are two components in G, diam(G) and rad(G) defined to be infinity ∞. Trivially, diam(G) ≤ 2 rad(G). Vertices with maximum eccentricity are called peripheral vertex. Vertices of minimum eccentricity form the center. A tree has at most two center vertices.
The Wiener index of a vertex v in a graph G, denoted by WG(v) is the sum of distances between v and all others. The Wiener index of a graph G, denoted by W(G), is the sum of distances over all pairs of vertices. An undirected graph's Wiener polynomial is defined to be Σ qd(u,v) over all unordered pairs of vertices u and v. Wiener index and Wiener polynomial are of particular interests to mathematical chemists.
The k-th power Gk of a graph G is a supergraph formed by adding an edge between all pairs of vertices of G with distance at most k. A second power of a graph is also called a square.
A k-spanner is a spanning subgraph in which every two vertices are at most k times as far apart on S than on G. The number k is the dilation. k-spanner is used for studying geometric network optimization.
[edit]
Genus
A crossing is a pair of intersecting edges. A graph is embeddable on a surface if its vertices and edges can be arranged on it without any crossing. The genus of a graph is the lowest genus of any surface on which the graph can embed.
A planar graph is one which can be drawn on the (Euclidean) plane without any crossing; and a plane graph, one which is drawn in such fashion. In other words, a planar graph is a graph of genus 0. The example graph is planar; the complete graph on n vertices, for n> 4, is not planar. Also, a tree is necessarily a planar graph.
When a graph is drawn without any crossing, any cycle that surrounds a region without any edge reaching from the cycle inside to such region forms a face. Two faces on a plane graph are adjacent if they share a common edge. A dual, or planar dual when the context needs to be clarified, G* of a plane graph G is a graph whose vertices represent the faces, including any outerface, of G and are adjacent in G* if and only if their corresponding faces are adjacent in G. The dual of a planar graph is always a planar pseudograph (e.g. consider the dual of a triangle). In the familiar case of a 3-connected simple planar graph G (isomorphic to a convex polyhedron P), the dual G* is also a 3-connected simple planar graph (and isomorphic to the dual polyhedron P*).
Furthermore, since we can establish a sense of "inside" and "outside" on a plane, we can identify an "outermost" region that contains the entire graph if the graph does not cover the entire plane. Such outermost region is called an outer face. An outerplanar graph is one which can be drawn in the planar fashion such that its vertices are all adjacent to the outer face; and an outerplane graph, one which is drawn in such fashion.
The minimum number of crossings that must appear when a graph is drawn on a plane is called the crossing number.
The minimum number of planar graphs needed to cover a graph is the thickness of the graph.
[edit]
Weighted graphs and networks
A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers. They may be restricted to rational numbers or integers. Certain algorithms require further restrictions on weights; for instance, the Dijkstra algorithm works properly only for positive weights. The weight of a path or the weight of a tree in a weighted graph is the sum of the weights of the selected edges. Sometimes a non-edge is labeled by a special weight representing infinity. Sometimes the word cost is used instead of weight. When stated without any qualification, a graph is always assumed to be unweighted. In some writings of graph theory the term network is a synonym for a weighted graph. A network may be directed or undirected, it may contain special vertices (nodes), such as source or sink. The classical network problems include:
•	minimum cost spanning tree, 
•	shortest paths, 
•	maximal flow (and the max-flow min-cut theorem) 
[edit]
Direction
An arc, or directed edge, is an ordered pair of endvertices. In such ordered pair, the first vertex is called a head, or initial vertex; and the second one, a tail, or terminal vertex. It can be thought of as an edge associated with a direction, namely designating a head and a tail to the endvertices. An undirected edge disregards any sense of direction and treats both endvertices interchangeably. A loop in a digraph, however, keeps a sense of direction and treats both head and tail identically. A set of arcs are multiple, or parallel, if they share the same head and the same tail. A pair of arcs are anti-parallel if one's head/tail is the other's tail/head. A digraph, or directed graph, is analogous to an undirected graph except that it contains at least one arc. An oriented graph contains only arcs. When stated without any qualification, a graph is almost always assumed to be undirected. Also, a digraph is usually assumed to contain no undirected edges.
A digraph is called simple if it has no loops and at most one arc between any pair of vertices. When stated without any qualification, a digraph is usually assumed to be simple.
In a digraph Γ, we distinguish the out degree dΓ+(v), the number of edges leaving a vertex v, and the in degree dΓ-(v), the number of edges entering a vertex v. The degree dΓ(v) of a vertex v is equal to the sum of its out- and in- degrees. When the context is clear, the subscript Γ can be dropped. Maximum and minimum out degrees are denoted by Δ+(Γ) and δ+(Γ); and maximum and minimum in degrees, Δ-(Γ) and δ-(Γ).
An out-neighborhood, or successor set, N+Γ(v) of a vertex v is the set of tails of arcs going from v. Likewise, an in-neighborhood, or predecessor set, N-Γ(v) of a vertex v is the set of heads of arc going into v.
A source is a vertex with 0 in-degree; and a sink, 0 out-degree.
A vertex v dominates another vertex u if there is an arc from v to u. A vertex subset S is out-dominating if every vertex not in S is dominated by some vertex in S; and in-dominating if every vertex in S is dominated by some vertex not in S.
A kernel is an independent out-dominating set. A digraph is kernel perfect if every induced sub-digraph has a kernel.
An Eulerian digraph is a digraph with equal in- and out-degrees at every vertex.
An orientation is an assignment of directions to the edges of an undirected or partially directed graph. When stated without any qualification, it is usually assumed that all undirected edges are replaced by a directed one in an orientation. Also, the underlying graph is usually assumed to be undirected and simple.
A tournament is a digraph in which each pair of vertices is connected by exactly one arc. In other words, it is an oriented complete graph.
A directed path, or just a path when the context is clear, is an oriented simple path such that all arcs go the same direction, meaning all internal vertices have in- and out-degrees 1. A vertex v is reachable from another vertex u if there is a directed path that starts from u and ends at v. Note that in general the condition that u is reachable from v does not imply that v is also reachable from u.
A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs. On the contrary, a diagraph is weakly connected if its underlying undirected graph is connected. A weakly connected graph can be thought of as a digraph in which every vertex is "reachable" from every other but not necessarily following the directions of the arcs. A strong orientation is an orientation that produces a strongly connected digraph.
A directed cycle, or just a cycle when the context is clear, is an oriented simple cycle such that all arcs go the same direction, meaning all vertices have in- and out-degrees 1. A digraph is acyclic if it does not contain any directed cycle. A finite, acyclic digraph with no isolated vertices necessarily contain at least one source and at least one sink. See also directed acyclic graph (dag for short) for more.
An arborescence, or out-tree or branching, is an oriented tree in which all vertices are reachable from a single vertex. Likewise, an in-tree is an oriented tree in which a single vertex is reachable from every other one.
[edit]
Various
A graph invariant is a property of a graph G, usually a number or a polynomial, that depends only on the isomorphism class of G. Examples are graph genus and graph order.
[edit]
To be merged
Note that prior to the introduction of large computer networks, graph theory was largely a field without widespread interest or application. Since network analysis has become a vital commercial interest, non-academics have crowded the field and popularized certain terms.
graph, network  
An abstraction of relationships among objects. Graphs consist exclusively of nodes and edges. All characteristics of a system are either eliminated or subsumed into these elements. 
diagram  
A visible rendering of the abstract concept of a graph. 
point, node, vertex  
Objects ("things") represented in a graph. These are almost always rendered as round dots. 
edge, link, arc  
Relationships represented in a graph. These are always rendered as straight or curved lines. The term "arc" may be misleading. 
unidentified  
Nodes or edges which are not considered as individuals. Only the way in which they connect to the rest of the graph characterize unidentified nodes and edges. 
color, colored, identified  
Nodes or edges which are considered as individuals. Although they may actually be rendered in diagrams in different colors, working mathematicians generally pencil in numbers or letters. 
undirected  
A graph in which each edge symbolizes an unordered, transitive relationship between two nodes. Such edges are rendered as plain lines or arcs. 
directed, digraph  
A graph in which each edge symbolizes an ordered, non-transitive relationship between two nodes. Such edges are rendered with an arrowhead at one end of a line or arc. 
unweighted  
A graph in which all the relationships symbolized by edges are considered equivalent. Such edges are rendered as plain lines or arcs. 
weighted (edge)  
Weighted edges symbolize relationships between nodes which are considered to have some value, for instance, distance or lag time. Such edges are usually annotated by a number or letter placed beside the edge. 
weighted (vertex)  
Weighted nodes have some value different from their identification. 
adjacent  
Two edges are adjacent if they have a node in common; two nodes are adjacent if they have an edge in common. 
degree  
The number of edges which connect a node. 
regular  
A graph in which each node has the same degree. 
complete  
A graph in which every node is linked to every other node. For a complete digraph, this means one link in either direction. 
route  
A sequence of edges and nodes from one node to another. Any given edge or node might be used more than once. 
path  
A route that does not pass any edge more than once. If the path does not pass any node more than once, it is a simple path. 
connected  
If some route exists from every node to every other, the graph is connected. Note that some graphs are not connected. A diagram of an unconnected graph may look like two or more unrelated diagrams, but all the nodes and edges shown are considered as one graph. 
loop, cycle  
A path which ends at the node where it began. 
tree  
A connected graph with no loops. 
Eulerian path  
A path which passes through every edge (once and only once). If the starting and ending nodes are the same, it is an Euler cycle or an Euler circuit. If the starting and ending nodes are different, it is an Euler trail. 
Hamiltonian path  
A path which passes through every node once and only once. If the starting and ending nodes are adjacent, it is a Hamiltonian cycle. 
[edit]

Area types
An OSPF network is divided into areas. These are logical groupings of routers whose information may be summarized towards the rest of the network. Several "special" area types are defined:
[edit]
Backbone area
The backbone area (also known as area zero) forms the core of an OSPF network. All other areas are connected to it, and inter-area routing happens via a router connected to the backbone area.
[edit]
Stub area
A stub area is an area which does not receive external routes. External routes are defined as routes which were distributed in OSPF via another routing protocol. Therefore, stub areas typically need to rely on a default route to send traffic to routes outside the present domain.
[edit]
Totally stubby area
A totally stubby area (TSA) is similar to a stub area, however this area does not allow summary routes in addition to the external routes, that is, inter-area (IA) routes are not summarized into totally stubby areas. The only way for traffic to get routed outside of the area is a default route which is the only Type-3 LSA advertised into the area. When there is only one route out of the area, fewer routing decisions have to be made by the route processor, which lowers system resource utilization.
[edit]
Not-so-stubby area
A not-so-stubby area (NSSA) is a type of stub area that can import autonomous system (AS) external routes and send them to the backbone, but cannot receive AS external routes from the backbone or other areas. Cisco also implements a proprietary version of a NSSA called a NSSA totally stubby area. It takes on the attributes of a TSA, meaning that type 3 and type 4 summary routes are not flooded into this type of area.
[edit]
OSPF router types
OSPF defines various router types. These are logical definitions, and a router that uses OSPF may be classified as more than one of the following types. For example, a router that is connected to more than one area, and which receives routes from a BGP process connected to another AS, is both an ABR and an ASBR.
[edit]
Area border router
An area border router (ABR) is a router that connects one or more OSPF areas to the main backbone network. It is considered a member of all areas it is connected to. An ABR keeps multiple copies of the link-state database in memory, one for each area.
[edit]
Autonomous system boundary router
An autonomous system boundary router (ASBR) is a router that is connected to more than one AS and that exchanges routing information with routers in other AS's. ASBR's typically also run a non-IGP routing protocol, such as BGP. An ASBR is used to distribute routes received from other ASs throughout its own AS.
[edit]
Internal router
A router is called an internal router (IR) if it has only OSPF adjacencies with routers in the same area.
[edit]
Backbone router
A backbone router (BR) is a router with an interface to the backbone area. An ABR is a BR, though the converse need not be true.
[edit]
Designated router
A designated router (DR) is the router elected by the network by elections. The DR is elected based on the following default criteria:
•	If the priority setting on a OSPF router is set to 0, that means it can NEVER become a DR or BDR. 
•	When a DR fails and the BDR takes over, there is another election to see who becomes the replacement BDR. 
•	The router sending the Hello packets with the highest priority. 
•	If two or more routers tie with the highest priority setting, the router sending the Hello with the highest RID (Router ID) wins. 
•	(NOTE) A RID is the highest logical (loopback) IP address configured on a router, if no logical/loopback IP address is set then the Router uses the highest IP address configured on its interfaces. (e.g. 192.168.0.1 would be higher than 10.1.1.2) 
•	Usually the router with the second highest priority number becomes the BDR (Backup Designated Router) 
•	The range of priority values range from 1 - 255, with a higher value increasing it's chances of becoming DR or BDR. 
•	IF a HIGHER priority OSPF router comes online AFTER the election has taken place, it will not become DR or BDR until (at least) the DR and BDR fail. 
DR's exist for the purpose of reducing network traffic by providing a source for routing updates, the DR maintains a complete topology table of the network and sends the updates to the other routers via multicast. This way all the routers do not have to constantly update each other, and can rather get all their updates from a single source. The use of multicasting further reduces the network load. DRs and BDRs are always setup/elected on Broadcast networks (Ethernet). DR's can also be elected on NBMA (Non-broadcast Multi-Access Networks) such as Frame Relay. DRs or BDRs do not configure on point-to-point links (such as a point-to-point WAN connection) because the bandwidth between two hosts cannot be further optimized.
[edit]
Backup designated router
A backup designated router (BDR) is a router that becomes the designated router if the current designated router has a problem or fails. The BDR is the OSPF router with second highest priority.

Travelling salesman problem
From Wikipedia, the free encyclopedia
(Redirected from Traveling salesman problem)
Jump to: navigation, search

It has been suggested that Wandering salesman problem be merged into this article or section. (Discuss)
The travelling salesman problem1 (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are hard to solve.
Contents
•	1 Problem statement 
•	2 Computational complexity 
•	3 NP-hardness 
•	4 Algorithms 
o	4.1 Exact algorithms 
o	4.2 Heuristics 
•	4.2.1 Constructive heuristics 
•	4.2.2 Iterative improvement 
•	4.2.3 Randomized improvement 
o	4.3 Special cases 
•	4.3.1 Restricted locations 
•	4.3.2 Triangle inequality and the Christofides algorithm 
•	4.3.3 Euclidean TSP 
•	4.3.4 Asymmetric TSP 
•	5 Note 
•	6 References 
•	7 See also 
•	8 External links 	
[edit]
Problem statement
Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?
An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight.
It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.
A related problem is the bottleneck traveling salesman problem (bottleneck TSP): Find a Hamiltonian cycle in a weighted graph with the minimal length of the longest edge.
The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in printed circuit manufacturing: scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem).
[edit]
Computational complexity
The most direct solution would be to try all the permutations (ordered combinations) and see which one is cheapest (using brute force search), but given that the number of permutations is n! (the factorial of the number of cities, n), this solution rapidly becomes impractical.
Using the techniques of dynamic programming, one can solve the problem exactly in time O(2n). Although this is exponential, it is still much better than O(n!). See Big O notation.
[edit]
NP-hardness
The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see the function problem article), and the decision problem version ("given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NP-complete.
The bottleneck traveling salesman problem is also NP-hard.
The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases.
Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case an optimal tour visits cities only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would decrease the tour length).
[edit]
Algorithms
The traditional lines of attack for the NP-hard problems are the following:
•	Devising algorithms for finding exact solutions (they will work reasonably fast only for relatively small problem sizes). 
•	Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal. 
•	Finding special cases for the problem ("subproblems") for which either exact or better heuristics are possible. 
For benchmarking of TSP algorithms, TSPLIB a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits.
[edit]
Exact algorithms
•	Various branch-and-bound algorithms, which can be used to process TSPs containing 40-60 cities. 
•	Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 120-200 cities. 
•	Recent implementations of branch-and-bound and cut based on linear programming works very well for up to 5,000 cities, and this approach has been used to solve instances with up to 33,810 cities. 
An exact solution for 15,112 German cities from TSPLIB was found in 2001 using the cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer Johnson in 1954, based on linear programming. The computations were performed on a network of 110 processors located at Rice University and Princeton University (see the Princeton external link). The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor. In May 2004, the traveling salesman problem of visiting all 24,978 cities in Sweden was solved: a tour of length approximately 72,500 kilometers was found and it was proven that no shorter tour exists.
In March 2005, the traveling salesman problem of visiting all 33,810 points in a circuit board was solved using CONCORDE: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists, the computation took approximately 15.7 CPU years.
[edit]
Heuristics
Various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2-3% away from the optimal solution.
Several categories of heuristics are recognized.
[edit]
Constructive heuristics
•	The nearest neighbor algorithm, which is normally fairly close to the optimal route, and does not take too long to execute. Unfortunately, it is provably reliable only for special cases of the TSP. In the general case, there exists an example[citation needed] for which the nearest neighbor algorithm gives the worst possible route. In practice, this heuristic provides solutions which are in average 10 to 15 percent above the optimal. 
[edit]
Iterative improvement
•	Pairwise exchange, or Kernighan-Lin heuristics. 
•	k-opt heuristic: Take a given tour and delete k mutually disjoint edges. Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, don't connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler problem. Each fragment endpoint can be connected to 2k − 2 other possibilities: of 2k total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2k-city TSP can then be solved with brute force methods to find the least-cost recombination of the original fragments. 
[edit]
Randomized improvement
•	Optimized Markov chain algorithms which utilize local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700-800 cities. 
TSP is a touchstone for many general heuristics devised for combinatorial optimization: genetic algorithms, simulated annealing, Tabu search, neural nets, ant system.
[edit]
Special cases
[edit]
Restricted locations
•	A trivial special case is when all cities are located on the perimeter of a convex polygon. 
•	A good exercise in combinatorial algorithms is to solve the TSP for a set of cities located along two concentric circles. 
[edit]
Triangle inequality and the Christofides algorithm
A very natural restriction of the TSP is the triangle inequality. That is, for any 3 cities A, B and C, the distance between A and C must be at most the distance from A to B plus the distance from B to C. Most natural instances of TSP satisfy this constraint.
In this case, there is a constant-factor approximation algorithm (due to Christofides, 1975) which always finds a tour of length at most 1.5 times the shortest tour. In the next paragraphs, we explain a weaker (but simpler) algorithm which finds a tour of length at most twice the shortest tour.
The length of the minimum spanning tree of the network is a natural lower bound for the length of the optimal route. In the TSP with triangle inequality case it is possible to prove upper bounds in terms of the minimum spanning tree and design an algorithm that has a provable upper bound on the length of the route. The first published (and the simplest) example follows.
•	Step 1: Construct the minimal spanning tree. 
•	Step 2: Duplicate all its edges. That is, wherever there is an edge from u to v, add a second edge from u to v. This gives us an Eulerian graph. 
•	Step 3: Find a Eulerian cycle in it. Clearly, its length is twice the length of the tree. 
•	Step 4: Convert the Eulerian cycle into the Hamiltonian one in the following way: walk along the Eulerian cycle, and each time you are about to come into an already visited vertex, skip it and try to go to the next one (along the Eulerian cycle). 
It is easy to prove that the last step works. Moreover, thanks to the triangle inequality, each skipping at Step 4 is in fact a shortcut, i.e., the length of the cycle does not increase. Hence it gives us a TSP tour no more than twice as long as the optimal one.
Christofides algorithm follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight perfect matching. This gives a TSP tour which is at most 1.5 times the optimal. It is a long-standing (since 1975) open problem to improve 1.5 to a smaller constant. It is known, however, that there is no polynomial time algorithm that finds a tour of length at most 1/219 more than optimal, unless P = NP (Papadimitriou and Vempala, 2000). In the case of the bounded metrics, it is known, that there is no polynomial time algorithm that constructs a tour of length at most 1/388 more than optimal, unless P = NP (Engebretsen and Karpinski, 2001). The best known polynomial time approximation algorithm for the TSP problem with distances one and two finds a tour of length at most 1/7 more than optimal (Berman and Karpinski, 2006).
The Christofides algorithm was one of the first approximation algorithms, and was in part responsible for drawing attention to approximation algorithms as a practical approach to intractable problems. As a matter of fact, the term "algorithm" was not commonly extended to approximation algorithms until later. At the time of publication, the Christofides algorithm was referred to as the Christofides heuristic.
[edit]
Euclidean TSP
Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. Although the problem still remains NP-hard, it is known that there exists a subexponential time algorithm for it. Moreover, many heuristics work better.
Euclidean TSP is a particular case of TSP with triangle inequality, since distances in plane obey triangle inequality. However, it seems to be easier than general TSP with triangle inequality. For example, the minimum spanning tree of the graph associated with an instance of Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n log n) time for n points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly.
In general, for any c > 0, there is a polynomial-time algorithm that finds a tour of length at most (1 + c) times the optimal for geometric instances of TSP (Arora; Mitchell; Rao and Smith); this is called a polynomial-time approximation scheme. This result is an important theoretical algorithm but is not likely to be practical. Instead, heuristics with weaker guarantees are often used, but they also perform better on instances of Euclidean TSP than on general instances.
[edit]
Asymmetric TSP
In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from A to B is not equal to the distance from B to A is called asymmetric TSP. A practical application of an asymmetric TSP is route optimization using street-level routing (asymmetric due to one-way streets, slip-roads and motorways).