Maximum independent set problem facet of maximum independent set
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set 
  
    
      
        S
      
    
    {\displaystyle S}
   of vertices such that for every two vertices in 
  
    
      
        S
      
    
    {\displaystyle S}
  , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in 
  
    
      
        S
      
    
    {\displaystyle S}
  . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.A maximal independent set is an independent set that is not a proper subset of any other independent set.
A maximum independent set is an independent set of largest possible size for a given graph 
  
    
      
        G
      
    
    {\displaystyle G}
  . This size is called the independence number of 
  
    
      
        G
      
    
    {\displaystyle G}
   and is usually denoted by 
  
    
      
        α
        (
        G
        )
      
    
    {\displaystyle \alpha (G)}
  . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
Every maximum independent set also is maximal, but the converse implication does not necessarily hold.In the maximum independent set problem, the input is an undirected graph, and the output is a maximum independent set in the graph. If there are multiple maximum independent sets, only one need be output. This problem is sometimes referred to as "vertex packing".
In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. The maximum independent set problem is the special case in which all weights are one.
In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets.
In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.The first three of these problems are all important in practical applications; the independent set decision problem is not, but is necessary in order to apply the theory of NP-completeness to problems related to independent sets.
aspect of element of feature of part of component of