A More Complicated Hardness Proof for Finding Densest Subgraphs in Bounded Degree Graphs
classification
💻 cs.CC
cs.DMmath.CO
keywords
degreegraphmaximumproblemboundedcomplicatedconsiderdensest
read the original abstract
We consider the Densest-Subgraph problem, where a graph and an integer k is given and we search for a subgraph on exactly k vertices that induces the maximum number of edges. We prove that this problem is NP-hard even when the input graph has maximum degree three.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.