@article{Konar_Sidiropoulos_2022, title={The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization}, volume={36}, url={https://ojs.aaai.org/index.php/AAAI/article/view/20325}, DOI={10.1609/aaai.v36i4.20325}, abstractNote={We introduce the triangle-densest-K-subgraph problem (TDKS) for undirected graphs: given a size parameter K, compute a subset of K vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge based densest-K-subgraph problem (DKS) to the case of higher-order network motifs. We prove that TDKS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDKS is submodular to construct a convex relaxation for the problem based on the Lovász extension for submodular functions. We demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DKS. We use document summarization to showcase why TDKS is a useful generalization of DKS.}, number={4}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Konar, Aritra and Sidiropoulos, Nicholas D.}, year={2022}, month={Jun.}, pages={4075-4082} }