Search for: All records

Abstract Given graph$$G=(V,E)$$ $G=(V,E)$with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ $k\ge 2$, our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ $k=2$and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem. 

Motivated by the importance of user engagement as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph [Formula: see text] and integers k and b, the maximum anchored k-core problem seeks to find a largest subset of vertices [Formula: see text] that induces a subgraph with at least [Formula: see text] vertices of degree at least k. We introduce a new integer programming (IP) formulation for the maximum anchored k-core problem and conduct a polyhedral study on the polytope of the problem. We show the linear programming relaxation of the proposed IP model is at least as strong as that of a naïve formulation. We also identify facet-defining inequalities of the IP formulation. Furthermore, we develop inequalities and fixing procedures to improve the computational performance of our IP model. We use benchmark instances to compare the computational performance of the IP model with (i) the naïve IP formulation and (ii) two existing heuristic algorithms. Our proposed IP model can optimally solve half of the benchmark instances that cannot be solved to optimality either by the naïve model or the existing heuristic approaches. Funding: This work is funded by the National Science Foundation (NSF) [Grant DMS-2318790] titled AMPS: Novel Combinatorial Optimization Techniques for Smartgrids and Power Networks. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2022.0024 .