Stability in graphs: methodologies and related problems

1965年，Edmonds发表了他著名的最大匹配问题的解，这是限制在线形图类中的最大独立（稳定）集问题的一种特殊情况。解决Edmonds的两个关键工具是增链和周期收缩。这两种工具都可以扩展到一般的图，但它们都没有被系统地研究或使用。本项目的想法是为这两种技术（增广图和图变换）奠定理论基础，以便将它们孤立的应用转化为一种成熟的方法，并应用这种方法来获得更快的指数时间算法，用于最大独立集和相关问题，如可满足性和约束满足。

In 1965, Edmonds published his celebrated solution to the maximum matching problem, which is a special case of the maximum independent (stable) set problem restricted to the class of line graphs. Two key tools in the solution of Edmonds are augmenting chains and cycle shrinking. Both tools can be extended to general graphs but neither of them has been studied or used on a systematic basis. The idea of the present project is to lay theoretical foundations for both techniques (augmenting graphs and graph transformations) in order to turn their isolated applications into a developed methodology and apply this methodology to obtain faster exponential time algorithms for the maximum independent set and related problems, such as satisfiability and constraint satisfaction.