Given a vertex-weighted undirected graph with blocking costs of its vertices and edges, we seek a minimum cost subset of vertices and edges to block such that the weight of any γ-quasi-clique in the interdicted graph is at most some predefined threshold parameter. The value of [Formula: see text] specifies the edge density of cohesive vertex groups of interest in the network. The considered weighted γ-quasi-clique interdiction problem can be viewed as a natural generalization of several variations of the clique blocker problem previously studied in the literature. From the application perspective, this setting is primarily motivated by the problem of disrupting adversarial (“dark”) networks (e.g., social or communication networks), where γ-quasi-cliques represent “tightly knit” groups of adversaries that we aim to dismantle. We first address the theoretical computational complexity of the problem. We then exploit some basic characterization of its feasible solutions to derive a linear integer programming (IP) formulation. This linear IP model can be solved using a lazy-fashioned branch-and-cut scheme. We also propose a combinatorial branch-and-bound algorithm for solving this problem. The computational performance of the developed exact solution schemes is studied using a test bed of randomly generated and real-life networks. Finally, some interesting insights and observations are also provided using a well-known example of a terrorist network. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: The work of S. Butenko was partially supported by the Air Force Office of Scientific Research under Award FA9550-23-1-0300. The work of O. A. Prokopyev was partially supported by the Office of Naval Research under Award ONR N00014-22-1-2678. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0027 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0027 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . The online appendix is available at https://doi.org/10.1287/ijoc.2023.0027 .

ABSTRACT This article proposes an implicit enumeration approach to solve the maximum ratio ‐plex and the maximum ratio ‐defective clique problems. The approach is inspired by the classical Bron‐Kerbosch algorithm for enumerating all maximal cliques in a graph, which is extended to enumerating structures that are hereditary on induced subgraphs. Such structures include ‐plexes and ‐defective cliques, among many others. The performance of the proposed approach is compared with that of the methods based on mixed integer linear programming (MILP), binary search, and Newton's iteration through numerical experiments on randomly generated and real‐life network instances.

Abstract Graph clustering is an important problem in network analysis. This problem can be approached by first finding a large cluster subgraph (i.e., a subgraph in which every connected component is a complete graph), perhaps in a relaxed form (connected components may have missing edges), and then assigning each of the remaining vertices to one of the connected components of the cluster subgraph according to some optimization criteria. The more vertices can be included in the initial cluster subgraph (also referred to as independent union of clusters), the more “clusterable” the graph is. This paper proposes a framework for establishing asymptotic bounds on the cardinality of independent unions of clusters in Erdős‐Rényi random graphs with constant , referred to as uniform random graphs. In particular, sufficient conditions ensuring (where is the number of nodes) upper bounds with probability 1 are developed and shown to be applicable for the maximum independent union of cliques as well as some clique relaxations. In addition, it is shown that every graph must have an independent union of cliques of cardinality at least . Since this bound is asymptotically tight on uniform random graphs, this suggests that these graphs can be viewed as a “least clusterable” class of graphs.

Abstract This article introduces and studies two clique relaxation models with fractional objectives: the maximum ratio ‐plex problem and the maximum ratio ‐defective clique problem. The decision version of each problem is shown to be strongly ‐complete; we also discuss some related computational complexity issues. The base optimization models are single‐ratio fractional 0‐1 problems. We describe two general types of solution methods: the first one is based on mixed‐integer linear programs (MILPs) obtained by linearizing the original nonlinear 0‐1 models; the other one exploits parametric methods (namely, a binary search and Newton's method) that solve MILPs in an iterative manner. For the proposed MILPs, we derive valid inequalities that are shown to substantially improve the performance of an off‐the‐shelf MILP solver. Finally, the considered solution approaches are compared via extensive numerical experiments using a set of artificially generated and real‐life network instances.

This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches.

This article considers the node‐weighted Steiner tree (NWST) problem and the maximum‐weight connected subgraph (MWCS) problem, which have applications in the design of telecommunication networks and the analysis of biological networks. Exact algorithms with provable worst‐case runtimes are provided. The first algorithm for NWST runs in time for n‐vertex instances when the number of terminals is bounded. It is based on dynamic programming and generalizes a Steiner tree algorithm of Dreyfus and Wagner. When used alongside Hakimi's spanning tree enumeration algorithm, it implies a time algorithm for NWST. It is also shown that Hakimi's 46‐year‐old algorithm for Steiner tree is essentially best‐possible under the strong exponential time hypothesis (SETH). Then two algorithms for MWCS are provided. Their runtimes are polynomial in the number of vertices of the graph, but exponential in the number of vertices that have positive (or negative) weight. The latter is shown to be essentially best‐possible under SETH. Together, they imply that MWCS can be solved in time . To the best of the authors’ knowledge, these are the first improvements over exhaustive search in the literature.

In this article, a heuristic is said to be provably best if, assuming , no other heuristic always finds a better solution (when one exists). This extends the usual notion of “best possible” approximation algorithms to include a larger class of heuristics. We illustrate the idea on several problems that are somewhat stylized versions of real‐life network optimization problems, including the maximum clique, maximum k‐club, minimum (connected) dominating set, and minimum vertex coloring problems. The corresponding provably best construction heuristics resemble those commonly used within popular metaheuristics. Along the way, we show that it is hard to recognize whether the clique number and the k‐club number of a graph are equal, yet a polynomial‐time computable function is “sandwiched” between them. This is similar to the celebrated Lovász function wherein an efficiently computable function lies between two graph invariants that are ‐hard to compute. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 238–245 2016

This paper considers the minimum k-connected d-dominating set problem, which is a fault-tolerant generalization of the minimum connected dominating set (MCDS) problem. Three integer programming formulations based on vertex cuts are proposed (depending on whether d < k, d = k, or d > k) and their integer hulls are studied. The separation problem for the vertex-cut inequalities is a weighted vertex-connectivity problem and is polytime solvable, meaning that the LP relaxation can be solved in polytime despite having exponentially many constraints. A new class of valid inequalities—r-robust vertex-cut inequalities—is introduced and is shown to induce exponentially many facets. Finally, a lazy-constraint approach is shown to compare favorably with existing approaches for the MCDS problem (the case k = d = 1), and is in fact the fastest in literature for standard test instances. A key subroutine is an algorithm for finding an inclusion-wise minimal vertex cut in linear time. Computational results for (k, d) = (2,1), (2,2), (3,3), (4,4) are provided as well.

This paper explores techniques for solving the maximum clique and vertex coloring problems on very large-scale real-life networks. Because of the size of such networks and the intractability of the considered problems, previously developed exact algorithms may not be directly applicable. The proposed approaches aim to reduce the network instances to a size that is tractable for existing solvers, while preserving optimality. Two clique relaxation structures are exploited for this purpose. In addition to the known k-core structure, a newly introduced clique relaxation, k-community, is used to further reduce the instance size. Experimental results on real-life graphs (collaboration networks, P2P networks, social networks, etc.) show the proposed procedures to be effective by finding, for the first time, exact solutions for instances with over 18 million vertices.