Bonchi, FrancescoGarcia-Soriano, DavidMiyauchi, AtsushiTsourakakis, Charalampos2022-08-182022-08-182021-12-31F. Bonchi, D. Garcia-Soriano, A. Miyauchi, C. Tsourakakis. 2021. "Finding densest k-connected subgraphs." Discrete Applied Mathematics. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2021.08.0320166-218Xhttps://hdl.handle.net/2144/45018Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph G = (V, E, w) we are asked to find S ⊆ V that maximizes the density d (S), i.e., half the weighted average degree of the induced subgraph G [S]. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph G = (V, E, w) and a positive integer/real k, we are asked to find S ⊆ V that maximizes the density d (S) under the constraint that G [S] is k-vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader’s theorem in graph theory and its extensions.en-US© 2021 Elsevier Inc. This version of the work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives International 4.0 License.http://creativecommons.org/licenses/by-nc-nd/4.0/Conference materials10.1016/j.dam.2021.08.032735067