Tscheuschner, Tobias: The complexity of local max-cut. 2012
Content
- Introduction
- Preliminaries
- Complexity of Local Max-Cut: Maximum Degree Four
- Overview of Contribution
- Basic Properties of Nodes with Maximum Degree Four
- P-hardness for Graphs with Nodes of Type I and III
- Is-Exp Property for Graphs with Nodes of Type I and III
- Enforcing Technique for Graphs with Nodes of Type I, II and III
- All-Exp Property
- PSPACE-completeness of the Standard Algorithm Problem
- Complexity of Local Max-Cut: Maximum Degree Five
- Overview of Contribution
- Usage of the P-hardness Reduction
- Substituting Certain Nodes of Unbounded Degree
- PLS-completeness
- Impact of the Results on Other Problems
- Conclusion and Open Problems
- Bibliography