VertexCover-problemet har visat sig vara svårt att beräkna på olika sätt: Det är NPfullständigt att hitta en optimal lösning och även NP-hård att hitta en approximation med rimliga faktorer. I kontrast, senaste experiment tyder på att på många verkliga nätverk kör tiden att lösa VertexCover är mycket mindre än även de mest kända FPT-approacher kan förklara. På samma sätt ger giriga algoritmer mycket bra approximationer till den optimala lösningen i praktiken, även om VertexCover är NP-hård att approximera inom rimliga faktorer. Vi kopplar dessa observationer till två egenskaper som observeras i många verkliga nätverk, nämligen en heterogen gradfördelning och hög klusterbildning. För att formalisera dessa egenskaper och förklara det observerade beteendet, analyserar vi hur en gren-och-minska algoritm utför på hyperboliska slumpmässiga grafer, som har blivit allt populärare för modellering av verkliga nätverk. I själva verket kan vi visa att VertexCover problem på hyperboliska slumpmässiga grafer kan lösas i polynom tid, med hög sannolikhet. Beviset bygger på intressanta strukturella egenskaper hos hyperboliska slumpmässiga grafer. Eftersom dessa förutsägelser av modellen är intressanta i sig, utförde vi experiment på verkliga nätverk som visar att dessa egenskaper också observeras i praktiken. När man använder samma strukturella egenskaper i en adaptiv girig algoritm, ytterligare experiment tyder på att detta leder till ännu bättre approximationer än standard girig strategi på verkliga fall.
Till exempel Bläsius et al. REF visar att minVC på hyperboliska slumpmässiga grafer kan lösas i polynom tid.
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}