Vi presenterar en polynom-rymd algoritm som beräknar antalet oberoende uppsättningar av någon ingång graf i tid O(1.1389 n ) för grafer med maximal grad 3 och i tid O(1.2356 n ) för allmänna grafer, där n är antalet hörn. Tillsammans med bland annat Björklund, Husfeldt och Koivisto (SIAM J. Comput. 2009], Detta leder till en snabbare polynom-rymd algoritm för graf färg problemet med körtid O(2.2356 n ). Som en biprodukt får vi också en exponentiellt utrymme O(1.2330 n ) tidsalgoritm för att räkna oberoende uppsättningar. Vår huvudalgoritm räknar oberoende uppsättningar i grafer med maximal grad 3 och ingen vertex med tre grannar av grad 3. Denna polynomalgoritm analyseras med hjälp av den nyligen införda separata, mät- och Conquer-metoden [Gaspers & Sorkin, ICALP 2015]. Med hjälp av Wahlströms sammansatta mätmetod kan denna förbättring av körtiden för småskaliga grafer sedan bootstrappas till större grader, vilket ger förbättringen för allmänna grafer. Att kombinera båda tillvägagångssätten leder till en viss oflexibilitet i valet av hörn att grena på för små-gradiga fall, som vi kontra med strukturella graf egenskaper. Den huvudsakliga komplikationen är att övre gräns antalet gånger algoritmen har att grena på hörn alla vars grannar har grad 2, samtidigt minska storleken på avskiljaren varje gång algoritmen grenar.
Eftersom den snabbaste kända polynom-rymd algoritm beräknar antalet oberoende uppsättningar med körtid O(1.2356 n ) REF, Det finns en polynom-rymd O(2.2356 n )-tid algoritm som beräknar det kromatiska numret.
Faster Graph Coloring in Polynomial Space
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}