Stable sets and polynomials
From MaRDI portal
The author surveys various applications of methods involving nonlinear commutative algebra to the stable set problem for graphs. In particular, he discusses a procedure for generating the facets of the stable set polytope. If a class of graphs \(G\) is such that all the facets of the stable set polytopes can be generated this way in a bounded number of steps, then the stability numbers of these graphs \(G\) are computable in polynomial time. Perfect, \(t\)-perfect, and \(h\)-perfect graphs have this property.
Recommendations
- scientific article; zbMATH DE number 4152524
- On stable and fixed polynomials
- Polynomials on stable spaces
- Some remarks on stable polynomials
- scientific article; zbMATH DE number 4132054
- Asymptotic stability for sets of polynomials.
- Stable polynomials over finite fields
- Stabilité des polynômes
- scientific article; zbMATH DE number 3937062
- scientific article; zbMATH DE number 772311
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Problem in Graph Theory
- A Theorem on k-Saturated Graphs
- Colorings and orientations of graphs
- Combinatorics and commutative algebra
- Compositions of Graphs and Polyhedra II: Stable Sets
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 3166040 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 16720 (Why is no real title available?)
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- scientific article; zbMATH DE number 3596866 (Why is no real title available?)
- scientific article; zbMATH DE number 3291000 (Why is no real title available?)
- Independence numbers of graphs and generators of ideals
- Matching theory
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On certain polytopes associated with graphs
- On the Shannon capacity of a graph
- Relaxations of vertex packing
- Stability critical graphs and ranks facets of the stable set polytope
- The perfectly matchable subgraph polytope of an arbitrary graph
Cited in
(49)- Stable multi-sets
- Algebraic proof systems over formulas.
- The stable set polytope and some operations on graphs
- Decomposition techniques applied to the clique-stable set separation problem
- A continuous characterization of the maximum vertex-weighted clique in hypergraphs
- Scheduling jobs on identical machines with agreement graph
- A note on greedy algorithms for the maximum weighted independent set problem
- Polynomially solvable cases for the maximum stable set problem
- Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares
- On stable and fixed polynomials
- Standard complexes of matroids and lattice paths
- On the complexity of Hilbert refutations for partition
- A note on Turán's theorem
- 2-colorability of \(r\)-uniform hypergraphs
- Hermitian matrices with a bounded number of eigenvalues
- Algebraic characterization of uniquely vertex colorable graphs
- Several notes on the power of Gomory-Chvátal cuts
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Maximum weighted induced subgraphs
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Some combinatorial applications of Gröbner bases
- Checking strict positivity of Kraus maps is NP-hard
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Stability of efficient sets: continuity of mobile polarities
- scientific article; zbMATH DE number 16720 (Why is no real title available?)
- Clique versus independent set
- On the stable solution of large scale problems over the doubly nonnegative cone
- Handelman's hierarchy for the maximum stable set problem
- A note on the reducedness and Gröbner bases of Specht ideals
- Communication complexity of pairs of graph families with applications
- scientific article; zbMATH DE number 4195980 (Why is no real title available?)
- Derivation radical subspace arrangements
- Independent sets from an algebraic perspective
- Invariant theoretic characterization of subdiscriminants of matrices
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Null- and Positivstellensatz proofs
- An algebraic formulation of hypergraph colorings
- Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
- Perfectly Matchable Set Polynomials and h^*-polynomials for Stable Set Polytopes of Complements of Graphs
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- First-order reasoning and efficient semi-algebraic proofs
- Parametric conic optimization problems over semidefinite plus nonnegative cone
- Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze
- An algebraic perspective on Ramsey numbers
- Nowhere-zero flow polynomials
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
- Low degree Nullstellensatz certificates for 3-colorability
- Composition of stable set polyhedra
This page was built for publication: Stable sets and polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313833)
