Lovász ϑ function, SVMs and finding dense subgraphs
Vinay Jethava, Anders Martinsson, Chiranjib Bhattacharyya, Devdatt Dubhashi · 2013
In this paper we establish that the Lovász ϑ function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM−ϑ graphs, on which Lovász ϑ function can be ap-proximated well by a Support vector machine (SVM). We show that Erdös-Rényi random G(n, p) graphs are SVM−ϑ graphs for log4 n n ≤ p< 1. Even if we embed a large clique of size Θ np