This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Independent set problem | |
|---|---|
| Name | Independent set problem |
| Field | Theoretical computer science, Graph theory, Combinatorics |
| Input | A finite simple graph G = (V, E) and an integer k |
| Question | Does G contain a set S ⊆ V of size at least k with no edges between vertices? |
Independent set problem The independent set problem asks whether a given finite simple graph contains a vertex set of specified size with no pair joined by an edge. It is a central decision problem in computability theory, complexity theory, and extremal graph theory, connecting results from reduction theory, algorithm design, and applications in operations research, information theory, and formal verification.
An instance consists of a finite simple graph G = (V, E) and an integer k; a solution is a subset S ⊆ V with |S| ≥ k such that no edge in E has both endpoints in S. The problem is closely related to maximum independent set, a function problem that seeks the largest such S, and to maximum clique via complementation of graphs, a relation used in reductions by Karp and others. Formal decision statements have been used in completeness proofs involving reductions from problems like Boolean satisfiability and 3-SAT in classical texts by Cook and Levin.
Independent set is NP-complete for general graphs, with NP-hardness shown by reductions from CLIQUE and 3-SAT in seminal work that established the P vs NP dichotomy. It is also complete for NP under polynomial-time many-one reductions described in foundational papers by Karp and consolidated in textbooks by Garey and Johnson. The optimization variant is NP-hard to approximate beyond certain thresholds, with inapproximability results connected to probabilistically checkable proofs used by researchers including Vazirani, Khot, and Arora.
Exact algorithms for special graph classes use structural decompositions studied by Seymour and Thomas, including dynamic programming on tree decompositions inspired by Alon and Yannakakis. Branch-and-bound and branching algorithms with improved exponential-time bounds have been developed in the tradition of work by Bellman and contemporary researchers like Fomin and Björklund. Integer programming formulations and cutting-plane methods leverage theory from Dantzig and Edmonds, while heuristic and metaheuristic approaches draw on methods from genetic algorithms, ant colony optimization, and evolutionary computation.
Many variants alter constraints or objective functions: weighted independent set (vertex weights) relates to problems studied by Safra; induced matching and induced forest variants connect to work by Lovász; bipartite, planar, and perfect graph restrictions invoke theorems by Dénes Kőnig and Berge. Generalizations include independence systems and matroid intersection frameworks developed by Edmonds and Whitney, and hypergraph independent set (transversal duality) treated in research by early combinatorialists and modern authors like Alon.
Independent set formulations appear in scheduling problems studied in operations research by Graham and Lawler, frequency assignment in telecommunications with roots in work by Niederreiter and Shannon, and register allocation in compilers influenced by designs from Knuth. Problems in computational biology, such as protein interaction network analysis, leverage techniques related to independent set and have ties to bioinformatics groups at institutions like NIH and EMBL. Resource allocation in wireless networks and task assignment in distributed systems invoke algorithmic frameworks advanced by researchers at Bell Labs and Massachusetts Institute of Technology.
Parameterized complexity studies treat independent set with parameter k, situating it in classes like W[1] and FPT via frameworks developed by Downey and Fellows. The problem is W[1]-complete under standard parameterizations, with kernelization lower bounds and fixed-parameter algorithms contributed by Niedermeier and Grandoni. Approximation algorithms attempt constant-factor or sublogarithmic guarantees; hardness of approximation results derive from PCP theorems attributed to Arora and Håstad, while positive approximation techniques use semidefinite programming and rounding schemes pioneered by Goemans and Williamson.
Independent set reduces to and from many classic problems: clique via graph complement, vertex cover via complementarity theorems in combinatorics referenced by Dénes Kőnig, and dominating set in parameterized reductions explored by Downey and Fellows. It is connected to constraint satisfaction problems like 3-SAT through NP-completeness proofs by Cook and reductions used in hardness frameworks by Karp. Approximation-preserving reductions link it to problems such as maximum cut studied by Allardice and semidefinite relaxations advanced by Vazirani.
Category:Graph theory problems