Abstrakt. Vi får asymptotiskt tighta algoritmiska gränser för Max-Cut och Edge Dominating Ställa problem på grafer av avgränsad klickbredd. Vi visar att på en n-vertex graf av klique-bredd t båda problemen (1) kan inte lösas i tid f (t)n o(t) för någon funktion f av t om inte exponentiella tidshypotesen misslyckas, och (2) kan lösas i tid n O(t). Nyckelord. exponentiell tidshypotes, klique-bredd, max-cut, kant dominerande uppsättning AMS ämnesklassificeringar. 05C85, 68R10, 68Q17, 68Q25, 68W40 DOI. 10,1137/130910932 1. Inledning. Trädbredd är en av de mest grundläggande parametrarna i grafalgoritmer. Grafer av avgränsad trädbredd har goda algoritmiska egenskaper som liknar träd, och det är därför många problem som är svåra på allmänna grafer kan lösas effektivt när inmatningen är begränsad till grafer av avgränsad trädbredd. Å andra sidan blir många svåra problem också dragbara när de begränsas till grafer "liknar kompletta grafer." Courcelle och Olarius [6] introducerade begreppet klickbredd som fångar fina algoritmiska egenskaper hos båda ytterligheterna. Sedan 2000 är forskningen om algoritmiska och strukturella aspekter av klickbredd en aktiv riktning i grafalgoritmer, logik och komplexitet. Corneil m.fl. [4] visar att grafer av klique-bredd högst 3 kan kännas igen i polynom tid. Genom metateorin i Courcelle, Makowsky och Rotics [5] är alla problem som kan uttryckas i M S 1 -logic (monadisk logik i andra ordningen på grafer med kvantifiering över undergrupper av hörn men inte av kanter) fasta parametern dragbar när parameteriserad av klique-bredden i en graf och uttryckens storlek. För många andra problem som inte kan uttryckas i denna logik, inklusive problem som Max-Cut, Edge Dominating Set, Graph Coloring, eller Hamiltonian Cycle, finns det en betydande mängd av den litteratur som ägnas åt algoritmer för dessa problem och deras generaliseringar på grafer av avgränsad klick-bredd
Fomin m.fl. REF visade att Maximum Cut är W[1]-hård men XP när parameteriserad av klique-bredd.
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}