Formal
definition of NP-completeness
A decision problem C is
NP-complete if:
- C is in NP, and
- Every problem in NP is reducible to C in polynomial time.
C
can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time.
Note that a problem satisfying condition 2 is said to be NP-hard,
whether or not it satisfies condition 1.
Example:
Graph coloring
In graph theory,
graph coloring is a special case
of graph
labeling; it is an assignment of labels traditionally called
"colors" to elements of a graph subject to certain constraints. In its
simplest form, it is a way of coloring the vertices of a graph such that no two
adjacent vertices share the same color; this is
called a vertex coloring.
Similarly, an edge coloring
assigns a color to each edge so that no two adjacent edges share the same
color, and a face coloring of a
planar graph assigns a color to each face or region so that no two faces that
share a boundary have the same color.
Vertex coloring
When used without
any qualification, a coloring of
a graph is almost always a proper
vertex coloring, namely a labelling of the graph’s vertices with
colors such that no two vertices sharing the same edge have the same color. Since a vertex with a
loop could never be properly colored, it is
understood that graphs in this context are loopless.
The
terminology of using colors for
vertex labels goes back to map coloring. Labels like red and blue are
only used when the number of colors is small, and normally it is understood
that the labels are drawn from the integers {1,2,3,...}.
A coloring using at most k colors is called a (proper) k-coloring. The smallest number of
colors needed to color a graph G
is called its chromatic number,
and is often denoted X(G).
Sometimes X(G) is used, since X(G) is also used to denote the
Euler characteristic of a graph. A graph
that can be assigned a (proper) k-coloring
is k-colorable, and it is k-chromatic if its chromatic number is
exactly k. A subset of vertices
assigned to the same color is called a color
class, every such class forms an independent set. Thus, a k-coloring is the same as a partition
of the vertex set into k
independent sets, and the terms k-partite
and k-colorable have the same
meaning.
The chromatic polynomial counts the number
of ways a graph can be colored using no more than a given number of colors. For
example, using three colors, the graph in the image to the right can be colored
in 12 ways. With only two colors, it cannot be colored at all. With four
colors, it can be colored in 24 + 4⋅12 = 72
ways: using all four colors, there are 4! = 24 valid colorings (every
assignment of four colors to any 4-vertex graph is a proper coloring);
and for every choice of three of the four colors, there are 12 valid
3-colorings. So, for the graph in the example, a table of the number of valid
colorings would start like this:
|
The chromatic
polynomial is a function P(G, t) that counts the number of t-colorings of G.
As the name indicates, for a given G
the function is indeed a polynomial in t.
For the example graph, P(G, t) = t(t − 1)2(t − 2), and indeed P(G, 4) = 72.
The
chromatic polynomial includes at least as much information about the
colorability of G as does the chromatic number. Indeed, χ is the
smallest positive integer that is not a root of the chromatic polynomial
X(G) = min {k : P(G,k) > 0 }
Chromatic
polynomials for certain graphs
Triangle K3
|
t( t-1 )(t-2)
|
t( t-1 )(t-2)....(t-(n-1))
|
|
Tree
with n vertices
|
t(t-1)n-1
|
Cycle Cn
|
(t-1)n+-1n(t-1)
|
(t-1)(t-2)(t7-12t6-67t5+230t4-529t3-814t2-775t-352
|
Edge coloring
An edge
coloring of a graph is a proper coloring of the edges, meaning an assignment of colors to edges so that no
vertex is incident to two edges of the same color. An edge coloring with k colors is called a k-edge-coloring and is equivalent to
the problem of partitioning the edge set into k matchings. The smallest number of colors
needed for an edge coloring of a graph G
is the chromatic index, or edge chromatic number, X(G).
Total coloring is a type of coloring on the vertices and edges of a graph. When used
without any qualification, a total coloring is always assumed to be proper in
the sense that no adjacent vertices, no adjacent edges, and no edge and its
endvertices are assigned the same color. The total chromatic number X’’(G) of a graph G is the
least number of colors needed in any total coloring of G.
Bounds on the chromatic number
Assigning distinct colors to distinct vertices always yields a proper coloring, so
1<= X(G) <= n
The only graphs that can be 1-colored are edgeless
graphs. A complete graph K of n vertices requires X (K)
= n colors. In an optimal
coloring there must be at least one of the graph’s m edges between every pair of color classes, so
X(G) (X(G) – 1)<= 2m
If G
contains a clique of size k, then at least k
colors are needed to color that clique; in other words, the chromatic number is
at least the clique number:
X(G) >= W(G)
For interval
graphs this bound is tight.
The 2-colorable graphs are exactly the bipartite
graphs, including trees and forests. By the four color theorem,
every planar graph can be 4-colored.
A greedy
coloring shows that every graph can be colored with one more color
than the maximum vertex degree,
X(G) <= #(G) + 1
Complete graphs have X(G)= n and #(G) = n-1, and odd cycles
have X(G) = 3and #(G) = 2, so for these graphs this bound is best
possible. In all other cases, the bound can be slightly improved; Brooks’ theorem states that
Brooks’ theorem:
X(G) <= #(G) for
a connected, simple graph G, unless G is a complete graph or an
odd cycle.
Polynomial time
Determining if a graph can be colored with
2 colors is equivalent to determining whether or not the graph is bipartite,
and thus computable in linear time using breadth-first search. More generally, the
chromatic number and a corresponding coloring of perfect
graphs can be computed in polynomial
time using semidefinite programming. Closed formulas for
chromatic polynomial are known for many classes of graphs, such as forest,
chordal graphs, cycles, wheels, and ladders, so these can be evaluated in
polynomial time.
If the graph is planar and has low branchwidth (or is
nonplanar but with a known branch decompositon), then it can be solved in
polynomial time using dynamic programming. In general, the time required is
polynomial in the graph size, but exponential in the branchwidth.
Exact algorithms
Brute-force search for a k-coloring considers every of the knassignments of k colors to n vertices and checks for each if it
is legal. To compute the chromatic number and the chromatic polynomial, this
procedure is used for every k = 1,2...n-1, impractical for all but the smallest
input graphs.
Using dynamic programming and a bound on the number
of maximal independent sets, k-colorability can be decided in time
and space O(2.445n). Using
the principle of inclusion–exclusion and Yates’s
algorithm for the fast zeta transform, k-colorability
can be decided in time O(2nn) for any k. Faster algorithms are known for 3- and 4-colorability, which
can be decided in time O(1.3289n) and O(1.7504n) respectively.
No comments:
Post a Comment