Clustering analysis of the ground-state structure of the vertex-cover problem

Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one obs...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2004-12, Vol.70 (6 Pt 2), p.066120-066120, Article 066120
Main Authors: Barthel, Wolfgang, Hartmann, Alexander K
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3
cites cdi_FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3
container_end_page 066120
container_issue 6 Pt 2
container_start_page 066120
container_title Physical review. E, Statistical, nonlinear, and soft matter physics
container_volume 70
creator Barthel, Wolfgang
Hartmann, Alexander K
description Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c
doi_str_mv 10.1103/physreve.70.066120
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_67245309</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>67245309</sourcerecordid><originalsourceid>FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3</originalsourceid><addsrcrecordid>eNpFkMtKw0AUhgdRbK2-gAvJyl3imZlkJllKqReoKKLrYZKcaSO51LkU-_amtOLq_HD-C3yEXFNIKAV-t1nvnMUtJhISEIIyOCFTmmUQMy7F6V7zIuYyyybkwrkvAM54np6TCc1EIdNUTsnLvA3Oo236VaR73e5c46LBRH6N0coOoa9j57XHyHkbKh8s_n23aD3-xNUwimhjh7LF7pKcGd06vDreGfl8WHzMn-Ll6-Pz_H4ZV2lOfSxLqCvNa6ozYEUJuSxEVdBUy5oCyzmIsmSIhgmDRsraUK0lllpCKqhmhs_I7aF33P0O6LzqGldh2-oeh-CUkCzNOBSjkR2MlR3cCMuojW06bXeKgtpDVG8jxHfcLpQEdYA4hm6O7aHssP6PHKnxXx3QcOQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>67245309</pqid></control><display><type>article</type><title>Clustering analysis of the ground-state structure of the vertex-cover problem</title><source>American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)</source><creator>Barthel, Wolfgang ; Hartmann, Alexander K</creator><creatorcontrib>Barthel, Wolfgang ; Hartmann, Alexander K</creatorcontrib><description>Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c&lt;e , the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a branch-and-bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e . For small connectivities, the solutions are collected in a finite small number of clusters, while the number of clusters diverges slowly with system size for larger connectivities and replica symmetry breaking, but not one-step replica symmetry breaking (1-RSB) occurs.</description><identifier>ISSN: 1539-3755</identifier><identifier>EISSN: 1550-2376</identifier><identifier>DOI: 10.1103/physreve.70.066120</identifier><identifier>PMID: 15697447</identifier><language>eng</language><publisher>United States</publisher><ispartof>Physical review. E, Statistical, nonlinear, and soft matter physics, 2004-12, Vol.70 (6 Pt 2), p.066120-066120, Article 066120</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3</citedby><cites>FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/15697447$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Barthel, Wolfgang</creatorcontrib><creatorcontrib>Hartmann, Alexander K</creatorcontrib><title>Clustering analysis of the ground-state structure of the vertex-cover problem</title><title>Physical review. E, Statistical, nonlinear, and soft matter physics</title><addtitle>Phys Rev E Stat Nonlin Soft Matter Phys</addtitle><description>Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c&lt;e , the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a branch-and-bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e . For small connectivities, the solutions are collected in a finite small number of clusters, while the number of clusters diverges slowly with system size for larger connectivities and replica symmetry breaking, but not one-step replica symmetry breaking (1-RSB) occurs.</description><issn>1539-3755</issn><issn>1550-2376</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2004</creationdate><recordtype>article</recordtype><recordid>eNpFkMtKw0AUhgdRbK2-gAvJyl3imZlkJllKqReoKKLrYZKcaSO51LkU-_amtOLq_HD-C3yEXFNIKAV-t1nvnMUtJhISEIIyOCFTmmUQMy7F6V7zIuYyyybkwrkvAM54np6TCc1EIdNUTsnLvA3Oo236VaR73e5c46LBRH6N0coOoa9j57XHyHkbKh8s_n23aD3-xNUwimhjh7LF7pKcGd06vDreGfl8WHzMn-Ll6-Pz_H4ZV2lOfSxLqCvNa6ozYEUJuSxEVdBUy5oCyzmIsmSIhgmDRsraUK0lllpCKqhmhs_I7aF33P0O6LzqGldh2-oeh-CUkCzNOBSjkR2MlR3cCMuojW06bXeKgtpDVG8jxHfcLpQEdYA4hm6O7aHssP6PHKnxXx3QcOQ</recordid><startdate>20041201</startdate><enddate>20041201</enddate><creator>Barthel, Wolfgang</creator><creator>Hartmann, Alexander K</creator><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope></search><sort><creationdate>20041201</creationdate><title>Clustering analysis of the ground-state structure of the vertex-cover problem</title><author>Barthel, Wolfgang ; Hartmann, Alexander K</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2004</creationdate><toplevel>online_resources</toplevel><creatorcontrib>Barthel, Wolfgang</creatorcontrib><creatorcontrib>Hartmann, Alexander K</creatorcontrib><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><jtitle>Physical review. E, Statistical, nonlinear, and soft matter physics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Barthel, Wolfgang</au><au>Hartmann, Alexander K</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Clustering analysis of the ground-state structure of the vertex-cover problem</atitle><jtitle>Physical review. E, Statistical, nonlinear, and soft matter physics</jtitle><addtitle>Phys Rev E Stat Nonlin Soft Matter Phys</addtitle><date>2004-12-01</date><risdate>2004</risdate><volume>70</volume><issue>6 Pt 2</issue><spage>066120</spage><epage>066120</epage><pages>066120-066120</pages><artnum>066120</artnum><issn>1539-3755</issn><eissn>1550-2376</eissn><abstract>Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c&lt;e , the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a branch-and-bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e . For small connectivities, the solutions are collected in a finite small number of clusters, while the number of clusters diverges slowly with system size for larger connectivities and replica symmetry breaking, but not one-step replica symmetry breaking (1-RSB) occurs.</abstract><cop>United States</cop><pmid>15697447</pmid><doi>10.1103/physreve.70.066120</doi><tpages>1</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1539-3755
ispartof Physical review. E, Statistical, nonlinear, and soft matter physics, 2004-12, Vol.70 (6 Pt 2), p.066120-066120, Article 066120
issn 1539-3755
1550-2376
language eng
recordid cdi_proquest_miscellaneous_67245309
source American Physical Society:Jisc Collections:APS Read and Publish 2023-2025 (reading list)
title Clustering analysis of the ground-state structure of the vertex-cover problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T09%3A12%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Clustering%20analysis%20of%20the%20ground-state%20structure%20of%20the%20vertex-cover%20problem&rft.jtitle=Physical%20review.%20E,%20Statistical,%20nonlinear,%20and%20soft%20matter%20physics&rft.au=Barthel,%20Wolfgang&rft.date=2004-12-01&rft.volume=70&rft.issue=6%20Pt%202&rft.spage=066120&rft.epage=066120&rft.pages=066120-066120&rft.artnum=066120&rft.issn=1539-3755&rft.eissn=1550-2376&rft_id=info:doi/10.1103/physreve.70.066120&rft_dat=%3Cproquest_cross%3E67245309%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c481t-7b0dca3d1a5029b08796c914a7d1028306bb2eef26fef77df1aa7eba70461a2f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=67245309&rft_id=info:pmid/15697447&rfr_iscdi=true