%0 Book Section %1 statphys23_0534 %A Pretti, M. %A Weigt, M. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K cavity graph method percolation phase random statphys23 topic-11 transition %T Emergence of extensive $q$-regular subgraphs in random graphs: a statistical-physics approach %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=534 %X In the last few years, statistical-mechanical methods have turned out to be increasingly effective in analyzing and solving complex problems coming from graph theory and theoretical computer science. In this contribution, we investigate the computationally hard problem whether a random graph of finite average vertex degree possesses an extensively large $q$-regular subgraph, i.e., a subgraph having all degree-$q$ vertices. We reformulate this problem as a constraint-satisfaction problem, and solve it using the zero-temperature cavity method of statistical physics. Such an application is specially interesting for $q 3$, since in that case not only the problem of finding subgraphs but also the existence problem itself turns out to be NP complete (i.e., no known algorithm exists, which is able to solve it in polynomial time). For $q = 3$, we find that the first extensive $q$-regular subgraphs appear discontinuously at an average vertex degree $c_3reg 3.3546$ and contain immediately about 24\% of graph vertices. This transition is extremely close to (but different from) the well-known 3-core percolation point $c_3core 3.3509$. Conversely, for $q > 3$, the $q$-regular subgraph percolation threshold is found to coincide with the $q$-core one. These results contradict a conjecture put forth in the framework of the graph theory community. By a suitable (fugacity-like) control parameter, we also investigate upon the number of extensive subgraphs (quenched entropy) as a function of their size. Even in this case, the 3-regular subgraph behavior turns out to be peculiar. Indeed, preliminary results suggest that, for $q > 3$, an exponential number of maximal- and minimal-size $q$-regular subgraphs exist, whereas this is not the case for $q = 3$.

@incollection{statphys23_0534, abstract = {In the last few years, statistical-mechanical methods have turned out to be increasingly effective in analyzing and solving complex problems coming from graph theory and theoretical computer science. In this contribution, we investigate the computationally hard problem whether a random graph of finite average vertex degree possesses an extensively large $q$-regular subgraph, i.e., a subgraph having all degree-$q$ vertices. We reformulate this problem as a constraint-satisfaction problem, and solve it using the zero-temperature cavity method of statistical physics. Such an application is specially interesting for $q \geq 3$, since in that case not only the problem of finding subgraphs but also the existence problem itself turns out to be NP complete (i.e., no known algorithm exists, which is able to solve it in polynomial time). For $q = 3$, we find that the first extensive $q$-regular subgraphs appear discontinuously at an average vertex degree $c_\mathrm{3reg} \approx 3.3546$ and contain immediately about 24\% of graph vertices. This transition is extremely close to (but different from) the well-known 3-core percolation point $c_\mathrm{3core} \approx 3.3509$. Conversely, for $q > 3$, the $q$-regular subgraph percolation threshold is found to coincide with the $q$-core one. These results contradict a conjecture put forth in the framework of the graph theory community. By a suitable (fugacity-like) control parameter, we also investigate upon the number of extensive subgraphs (quenched entropy) as a function of their size. Even in this case, the 3-regular subgraph behavior turns out to be peculiar. Indeed, preliminary results suggest that, for $q > 3$, an exponential number of maximal- and minimal-size $q$-regular subgraphs exist, whereas this is not the case for $q = 3$.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Pretti, M. and Weigt, M.}, biburl = {https://www.bibsonomy.org/bibtex/27e2ac750f92f92e382c253c83a7c9e71/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {7ef3aa5c27652f8d42bd189557455088}, intrahash = {7e2ac750f92f92e382c253c83a7c9e71}, keywords = {cavity graph method percolation phase random statphys23 topic-11 transition}, month = {9-13 July}, timestamp = {2007-06-20T10:16:22.000+0200}, title = {Emergence of extensive $q$-regular subgraphs in random graphs: a statistical-physics approach}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=534}, year = 2007 }