En viktig fråga i studien av problem med begränsad tillfredsställelse (CSP) är att förstå hur grafen eller hypergrafen som beskriver begränsningarnas incidensstruktur påverkar problemets komplexitet. För binära CSP instanser (dvs., där varje begränsning endast omfattar två variabler), är situationen väl förstådd: komplexiteten i problemet beror i huvudsak på trädbredden i grafen av begränsningarna [19, 24]. Detta är dock inte rätt svar om begränsningar med obegränsat antal variabler är tillåtna, och i synnerhet för CSP-fall som härrör från problem med frågebedömning i databasteorin. Formellt, om H är en klass av hypergrafer, då låt CSP(H) vara CSP begränsas till fall vars hypergraf är i H. Vårt mål är att karakterisera de klasser av hypergrafer för vilka CSP(H) är polynom-tid solvable eller fast-parameter dragbar, parameterized av antalet variabler. I applikationer relaterade till databasförfrågan utvärdering, antar vi vanligtvis att antalet variabler är mycket mindre än storleken på instansen, vilket parameterisering av antalet variabler är en meningsfull fråga. Den mest allmänt kända egenskapen hos H som gör CSP(H) polynom-tid solvable är begränsad fraktionerad hypertree bredd. Här introducerar vi en ny hypergrafmått kallas submodulär bredd, och visar att avgränsad submodulär bredd av H (som är en strikt mer allmän egenskap än avgränsad fraktionerad hypertree bredd) innebär att CSP(H) är fastparameterdragbar. I en matchande hårdhet resultat, visar vi att om H har obunden submodulär bredd, då CSP(H) inte är fast-parameter dragbar (och därmed inte polynom tid lösbar), om inte Exponential Time Hypothesis (ETH) misslyckas. Det algoritmiska resultatet använder trädnedbrytningar på ett nytt sätt: istället för att använda en enda nedbrytning beroende på hypergrafen är instansen uppdelad i en uppsättning †forskning som stöds av ERC Advanced Grant DMMCA. * Den fullständiga versionen av tidningen finns på http://arxiv.org/abs/0911.0801 Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. fall (alla på samma uppsättning variabler som den ursprungliga instansen), och sedan de nya instanserna löses genom att välja en annan träd sönderdelning för var och en av dem. Anledningen till att denna strategi fungerar är att uppdelningen kan göras på ett sådant sätt att de nya instanserna är "uniforma" med avseende på antalet utvidgningar av partiella lösningar, och därför kan antalet partiella lösningar beskrivas av en submodulär funktion. För hårdhetsresultatet, bevisar vi via en serie av kombinatoriska resultat att om en hypergraf H har stor submodulär bredd, då en 3SAT instans kan effektivt simuleras av en CSP instans vars hypergraph är H. För att bevisa dessa kombinatoriska resultat, måste vi utveckla en teori om (multicommodity) flöden på hypergrafer och vertex-separatorer i fallet när funktionen b(S) definiera kostnaden för separator S är submodulär.
Situationen är annorlunda för fastparameterdragbarhet: Marx gav en fullständig klassificering av de fastparameterdragbara begränsningarna CSP(C, −), för klasser C av strukturer av obunden arity REF.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}