On solving the densest k-subgraph problem on large graphs

DOI10.1080/10556788.2019.1595620zbMATH Open1464.90086arXiv1901.06344OpenAlexW2962753098MaRDI QIDQ5859000FDOQ5859000

Authors: Renata Sotirov 

Publication date: 15 April 2021

Published in: Optimization Methods \& Software (Search for Journal in Brave)

Abstract: The densest $k$-subgraph problem is the problem of finding a $k$-vertex subgraph of a graph with the maximum number of edges. In order to solve large instances of the densest $k$-subgraph problem, we introduce two algorithms that are based on the random coordinate descent approach. Although it is common use to update at most two random coordinates simultaneously in each iteration of an algorithm, our algorithms may simultaneously update many coordinates. We show the benefit of updating more than two coordinates simultaneously for solving the densest $k$-subgraph problem, and solve large problem instances with up to $2^{15}$ vertices.

Full work available at URL: https://arxiv.org/abs/1901.06344

Recommendations

• The dense \(k\)-subgraph problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Finding Dense Subgraphs with Size Bounds
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem

zbMATH Keywords

large graphsdensest \(k\)-subgraph problemrandom coordinate descent algorithm

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Nonlinear programming (90C30)

Cites Work

• Using a conic bundle method to accelerate both phases of a quadratic convex reformulation
• A new polynomial-time algorithm for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Nuclear norm minimization for the planted clique and biclique problems
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Clustering and domination in perfect graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• \(k\)-edge subgraph problems
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• PTAS for densest \(k\)-subgraph in interval graphs
• Approximation algorithms for maximization problems arising in graph partitioning
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Subgradient methods for huge-scale optimization problems
• The dense \(k\)-subgraph problem
• A polynomial-time algorithm for a class of linear complementarity problems
• Title not available (Why is that?)
• Linear Programming in O([n3/ln n]L) Operations
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• Heuristic and Special Case Algorithms for Dispersion Problems
• Good solutions to discrete noxious location problems via metaheuristics
• Variable neighborhood search for the heaviest \(k\)-subgraph
• An application of tabu search heuristic for the maximum edge-weighted subgraph problem
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Solving \(k\)-cluster problems to optimality with semidefinite programming
• Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
• Different Formulations for Solving the HeaviestK-Subgraph Problem
• Title not available (Why is that?)
• Finding Dense Subgraphs with Size Bounds
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Title not available (Why is that?)
• Random block coordinate descent methods for linearly constrained optimization over networks
• An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem

Cited In (10)

• Title not available (Why is that?)
• A note on the approximability of the dense subgraph problem.
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• In search of dense subgraphs: How good is greedy peeling?
• On convergence of a \(q\)-random coordinate constrained algorithm for non-convex problems
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Convex optimization for the densest subgraph and densest submatrix problems
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Practical parallel algorithms for near-optimal densest subgraphs on massive graphs
• Computing the \(k\) densest subgraphs of a graph

Uses Software

• MIQCR-CB

This page was built for publication: On solving the densest \(k\)-subgraph problem on large graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859000)