Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910365809377280 |
|---|---|
| author | Santos, Daniela Scherer dos Klamroth, Kathrin Martins, Pedro Paquete, Luís |
| author_facet | Santos, Daniela Scherer dos Klamroth, Kathrin Martins, Pedro Paquete, Luís |
| contents | Given an undirected graph $G$, a quasi-clique is a subgraph of $G$ whose density is at least $γ$ $(0 < γ\leq 1)$. Two optimization problems can be defined for quasi-cliques: the Maximum Quasi-Clique (MQC) Problem, which finds a quasi-clique with maximum vertex cardinality, and the Densest $k$-Subgraph (DKS) Problem, which finds the densest subgraph given a fixed cardinality constraint. Most existing approaches to solve both problems often disregard the requirement of connectedness, which may lead to solutions containing isolated components that are meaningless for many real-life applications. To address this issue, we propose two flow-based connectedness constraints to be integrated into known Mixed-Integer Linear Programming (MILP) formulations for either MQC or DKS problems. We compare the performance of MILP formulations enhanced with our connectedness constraints in terms of both running time and number of solved instances against existing approaches that ensure quasi-clique connectedness. Experimental results demonstrate that our constraints are quite competitive, making them valuable for practical applications requiring connectedness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_08534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems Santos, Daniela Scherer dos Klamroth, Kathrin Martins, Pedro Paquete, Luís Discrete Mathematics Given an undirected graph $G$, a quasi-clique is a subgraph of $G$ whose density is at least $γ$ $(0 < γ\leq 1)$. Two optimization problems can be defined for quasi-cliques: the Maximum Quasi-Clique (MQC) Problem, which finds a quasi-clique with maximum vertex cardinality, and the Densest $k$-Subgraph (DKS) Problem, which finds the densest subgraph given a fixed cardinality constraint. Most existing approaches to solve both problems often disregard the requirement of connectedness, which may lead to solutions containing isolated components that are meaningless for many real-life applications. To address this issue, we propose two flow-based connectedness constraints to be integrated into known Mixed-Integer Linear Programming (MILP) formulations for either MQC or DKS problems. We compare the performance of MILP formulations enhanced with our connectedness constraints in terms of both running time and number of solved instances against existing approaches that ensure quasi-clique connectedness. Experimental results demonstrate that our constraints are quite competitive, making them valuable for practical applications requiring connectedness. |
| title | Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2403.08534 |