Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem
The densest <i>k</i>-subgraph (DkS) maximization problem is to find a set of <i>k</i> vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are pre...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/2/108 |
| _version_ | 1798003461991694336 |
|---|---|
| author | Chuan-Hao Guo Yuan Guo Bei-Bei Liu |
| author_facet | Chuan-Hao Guo Yuan Guo Bei-Bei Liu |
| author_sort | Chuan-Hao Guo |
| collection | DOAJ |
| description | The densest <i>k</i>-subgraph (DkS) maximization problem is to find a set of <i>k</i> vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios’ results are given for these relaxation problems. Finally, some numerical examples are tested to show the comparison of these relaxation problems, and the numerical results show that the doubly nonnegative relaxation is more promising than the semidefinite relaxation for solving some DkS problems. |
| first_indexed | 2024-04-11T12:08:00Z |
| format | Article |
| id | doaj.art-06235e297fbd469090f2157c1c4a5a75 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T12:08:00Z |
| publishDate | 2019-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-06235e297fbd469090f2157c1c4a5a752022-12-22T04:24:40ZengMDPI AGEntropy1099-43002019-01-0121210810.3390/e21020108e21020108Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph ProblemChuan-Hao Guo0Yuan Guo1Bei-Bei Liu2School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, ChinaSchool of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, ChinaSchool of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, ChinaThe densest <i>k</i>-subgraph (DkS) maximization problem is to find a set of <i>k</i> vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios’ results are given for these relaxation problems. Finally, some numerical examples are tested to show the comparison of these relaxation problems, and the numerical results show that the doubly nonnegative relaxation is more promising than the semidefinite relaxation for solving some DkS problems.https://www.mdpi.com/1099-4300/21/2/108densest <i>k</i>-subgraphdoubly nonnegative relaxationsemidefinite relaxationapproximation ratioNP-hard |
| spellingShingle | Chuan-Hao Guo Yuan Guo Bei-Bei Liu Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem Entropy densest <i>k</i>-subgraph doubly nonnegative relaxation semidefinite relaxation approximation ratio NP-hard |
| title | Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem |
| title_full | Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem |
| title_fullStr | Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem |
| title_full_unstemmed | Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem |
| title_short | Doubly Nonnegative and Semidefinite Relaxations for the Densest <i>k</i>-Subgraph Problem |
| title_sort | doubly nonnegative and semidefinite relaxations for the densest i k i subgraph problem |
| topic | densest <i>k</i>-subgraph doubly nonnegative relaxation semidefinite relaxation approximation ratio NP-hard |
| url | https://www.mdpi.com/1099-4300/21/2/108 |
| work_keys_str_mv | AT chuanhaoguo doublynonnegativeandsemidefiniterelaxationsforthedensestikisubgraphproblem AT yuanguo doublynonnegativeandsemidefiniterelaxationsforthedensestikisubgraphproblem AT beibeiliu doublynonnegativeandsemidefiniterelaxationsforthedensestikisubgraphproblem |