Kavli Affiliate: Yi Zhou
| First 5 Authors: Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao, Jin-Kao Hao
| Summary:
Given a graph, a $k$-plex is a set of vertices in which each vertex is not
adjacent to at most $k-1$ other vertices in the set. The maximum $k$-plex
problem, which asks for the largest $k$-plex from the given graph, is an
important but computationally challenging problem in applications such as graph
mining and community detection. So far, there are many practical algorithms,
but without providing theoretical explanations on their efficiency. We define a
novel parameter of the input instance, $g_k(G)$, the gap between the degeneracy
bound and the size of the maximum $k$-plex in the given graph, and present an
exact algorithm parameterized by this $g_k(G)$, which has a worst-case running
time polynomial in the size of the input graph and exponential in $g_k(G)$. In
real-world inputs, $g_k(G)$ is very small, usually bounded by $O(log{(|V|)})$,
indicating that the algorithm runs in polynomial time. We further extend our
discussion to an even smaller parameter $cg_k(G)$, the gap between the
community-degeneracy bound and the size of the maximum $k$-plex, and show that
without much modification, our algorithm can also be parameterized by
$cg_k(G)$. To verify the empirical performance of these algorithms, we carry
out extensive experiments to show that these algorithms are competitive with
the state-of-the-art algorithms. In particular, for large $k$ values such as
$15$ and $20$, our algorithms dominate the existing algorithms. Finally,
empirical analysis is performed to illustrate the effectiveness of the
parameters and other key components in the implementation.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=3