Unweighted Maximum Cut SWAP (UMCS)
Input
An undirected graph $G = (V, E)$.
Problem
Find a locally optimal subset of vertices.
Definitions
A subset is locally optimal if it has maximum cost among its neighbors. The cost is the sum of the number of edges leaving vertices in the subset; each edge has a weight of one. A neighbor of a subset $S$ is a set of size $|S|$ whose symmetric difference with $S$ contains one vertex.
Status
$\P$-hard or $\FP$-complete (Papadimitriou, Schäffer, and Yannakakis [1], Schäffer and Yannakakis [2]).
Remarks
The reduction to show hardness is from UNAE3SAT. The weighted version of the problem in which each edge is given an integer weight encoded in binary is $\mathsf{PLS}$-complete [1][2]. If the edge weights are encoded in unary, the problem is $\mathsf{FP}$-complete. The Different than Majority Labeling Problem is equivalent to this problem [2]. A different than majority labeling of an undirected graph $G = (V, E)$ is a labeling of the vertices with either $0$ or $1$ such that each vertex is labeled differently than at least half of its neighbors. Luby describes an $\NC$ algorithm for a related problem [3]. Sarnath and He show that a lexicographic version of the problem is $\P$-complete [4], see LFDTML.
References
- C. H. Papadimitriou, A. A. Schäffer, and M. Yannakakis (1990). On the complexity of local search.
- A. A. Sch¨affer and M. Yannakakis (1991). Simple local search problems that are hard to solve.
- M. Luby (1988). Removing randomness in parallel computation without a processor penalty.
- R. Sarnath and X. He (1990). A P-complete graph partition problem.
- G. Godbeer (1987). The computational complexity of the stable configuration problem for connectionist models.
- J. Lipscomb (1987). On the computational complexity of finding a connectionist model’s stable state vectors.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.5.4.