Stability in graphs: methodologies and related problems

点击翻译按钮获取中文摘要

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.