Kavli Affiliate: Yi Zhou
| First 5 Authors: Chunyu Luo, Yi Zhou, Zhengren Wang, Mingyu Xiao,
| Summary:
A $k$-defective clique of an undirected graph $G$ is a subset of its vertices
that induces a nearly complete graph with a maximum of $k$ missing edges. The
maximum $k$-defective clique problem, which asks for the largest $k$-defective
clique from the given graph, is important in many applications, such as social
and biological network analysis. In the paper, we propose a new branching
algorithm that takes advantage of the structural properties of the
$k$-defective clique and uses the efficient maximum clique algorithm as a
subroutine. As a result, the algorithm has a better asymptotic running time
than the existing ones. We also investigate upper-bounding techniques and
propose a new upper bound utilizing the textit{conflict relationship} between
vertex pairs. Because conflict relationship is common in many graph problems,
we believe that this technique can be potentially generalized. Finally,
experiments show that our algorithm outperforms state-of-the-art solvers on a
wide range of open benchmarks.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=3