FACTOID # 21: 15% of Army recruits from South Dakota are Native American, which is roughly the same percentage for female Army recruits in the state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Independent set problem

In mathematics, the independent set problem (IS) is a well-known problem in graph theory and combinatorics. The independent set problem is known to be NP-complete. It is almost identical to the clique problem. Image File history File links Mergefrom. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... A drawing of a graph. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. ...

Contents

Description

Given a graph G, an independent set is a subset of its vertices that are pairwise not adjacent. In other words, the subgraph induced by these vertices has no edges, only isolated vertices. Then, the independent set problem asks: given a graph G and a positive integer k, does G have an independent set of cardinality at least k? In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ...


The corresponding optimization problem is the maximum independent set problem, which attempts to find the largest independent set in a graph. Given a solution to the decision problem, binary search can be used to solve the optimization problem with O(log |V|) invocations of the decision problem's solution. The optimization problem is known to have no constant-factor approximation algorithm if P≠NP. In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ... In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...


Independent set problems and clique problems may be easily translated into each other: an independent set in a graph G is a clique in the complement graph of G, and vice versa. K5, a complete graph. ... In graph theory the complement or inverse of a graph is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in . ...


Algorithms

The simplest brute force algorithm for independent set simply examines every vertex subset of size at least k and checks whether it is an independent set. This requires n!/(n - k)!k! where n is the order of the graph. In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ...


A much easier problem to solve is that of finding a maximal independent set, which is an independent set not contained in any other independent set. We begin with a single vertex. We find a vertex not adjacent to it and add it, then find a vertex adjacent to neither of these and add it, and so on until we can find no more vertices to add. At this time the set is maximal independent. More complex algorithms are known for listing all maximal independent sets, but the number of such sets can be exponential in the number of vertices. This can be seen by constructing a graph containing n disconnected triangles. The maximum independent set is obviously of order n, taking one vertex from each triangle. The number of maximal independent sets is therefore 3n (Moon & Moser 1965). In graph theory, an independent set is a set of nodes on a graph such that no edge is complete. ...


Proof of NP-completeness

It's easy to see that the problem is in NP, since if we have a subset of vertices, we can check to make sure there are no edges between any two of them in polynomial time. To show the problem is NP-hard, we will use a reduction from another NP-complete problem.


Assume we already know Cook's result that the boolean satisfiability problem is NP-complete. One can efficiently reduce any boolean formula to conjunctive normal form (CNF). In conjunctive normal form: 3SAT redirects here. ... In boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ...

  • The formula is a conjunction (and) of clauses.
  • Each clause is a disjunction (or) of literals.
  • Each literal is either a variable or its negation.

For example, the following formula is in CNF form, where ~ denotes negation:

(x1 or ~x2 or ~x3) and (x1 or x2 or x4)

Such a formula is satisfiable if we can assign true/false values to each variable in such a way that at least one literal in every clause is true. For example, any assignment with x2 false and x4 true satisfies the above formula. The problem of determining whether a formula in CNF form is satisfiable is also NP-complete and is called CNF-SAT.

The graph constructed by this reduction for the example formula above
The graph constructed by this reduction for the example formula above

Now, we describe a polynomial-time many-one reduction from CNF-SAT to the independent set problem. First, create a vertex for every literal in the formula; include duplicate vertices for those occurring more than once. Put an edge between: Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...

  1. Any two literals which are negations of one another.
  2. Any two literals which are in the same clause.

For example, in our example above, x2 would be adjacent to ~x2, the first x1 would be adjacent to ~x2, and the second x1 would be adjacent to x4.


We argue now that this graph has an independent set of size at least k, where k is the number of clauses, if and only if the original formula was satisfiable.


Suppose we have an assignment satisfying the original formula. Then we can choose one literal from each clause which is made true by this assignment. This set is independent, because it only includes one literal from each clause (no edges of type 2), and because no assignment makes both a literal and its negation true (no edges of type 1).


On the other hand, suppose we have an independent set of size k or greater. It can't contain any two literals in the same clause, since these are pairwise adjacent. But then, since there are at least k vertices and k clauses, we must have at least one in each clause (in fact exactly one). It also can't contain both a literal and its negation, because there are edges between these. That means it's easy to choose an assignment that makes these k clauses all true, and this assignment will satisfy the original formula.


What makes this reduction to independent set so simple is the capacity of the edges in the graph to express constraints, such as the necessity of never choosing both a literal and its negation. The graph coloring problem also benefits from this useful property. A 3-coloring suits this graph, but fewer colors would result in adjacent verticies of the same color. ...


References

  • Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.2: GT20, pg.194.
  • Moon, J. W. & Moser, L. (1965), "On cliques in graphs", Israel J. Math. 3: 23–28, MR0182577

Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... Leo Moser (April 11, 1921—February 9, 1970) was an Austrian-Canadian mathematician, best known for his polygon notation. ... Mathematical Reviews is a scientific journal edited by the American Mathematical Society offering reviews of recent mathematical papers. ...

External links

  • http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
  • Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring

  Results from FactBites:
 
NationMaster - Encyclopedia: Independent Set problem (1339 words)
In mathematics, the independent set problem (IS) is a well-known problem in graph theory and combinatorics.
Given a graph G, an independent set is a subset of its vertices that are pairwise not adjacent.
It fact, the independent set problem and the clique problem are equivalent, in the sense that if we know one is NP-complete, we can easily show that the other is NP-complete, and most algorithms for solving one problem can be transformed into an algorithm which solves the other in the same time and space.
Independent Set (635 words)
Independent sets avoid conflicts between elements and hence arise often in coding theory and scheduling problems.
The independent set problem is in some sense dual to the graph matching problem.
The maximum independent set of a tree can be found in linear time by   (1) stripping off the leaf nodes, (2) adding them to the independent set, (3) deleting the newly formed leaves, and then (4) repeating from the first step on the resulting tree until it is empty.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m