  We present a quantum-inspired classical algorithm that can be used for
graph-theoretical problems, such as finding the densest $k$-subgraph and
finding the maximum weight clique, which are proposed as applications of a
Gaussian boson sampler. The main observation from Gaussian boson samplers is
that a given graph's adjacency matrix to be encoded in a Gaussian boson sampler
is nonnegative, which does not necessitate quantum interference. We first
provide how to program a given graph problem into our efficient classical
algorithm. We then numerically compare the performance of ideal and lossy
Gaussian boson samplers, our quantum-inspired classical sampler, and the
uniform sampler for finding the densest $k$-subgraph and finding the maximum
weight clique and show that the advantage from Gaussian boson samplers is not
significant in general. We finally discuss the potential advantage of a
Gaussian boson sampler over the proposed sampler.
