Low Degree Subgraph (LDS)
Category: Circuit Complexity
Input
An undirected graph $G = (V, E)$ and an integer $k$.
Problem
Find a maximal induced subgraph with maximum degree at most $k$.
Status
Open (Godbeer [1], Greenlaw [2]).
Remarks
The Maximal Independent Set Problem is a LDS with $k$ equal to zero, see LFMIS. Godbeer shows that LDS can be viewed as a Connectionist Model problem in which edge weights have value $-1$ [1], see SCCM. Two decision problems based on low degree subgraph computations are proved $\NP$-complete in [2].
References
- G. Godbeer (1987). The computational complexity of the stable configuration problem for connectionist models.
- R. Greenlaw (1989). Ordered vertex removal and subgraph problems.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.1.5.