Vi visar att ett antal grafteoretiska räkneproblem fortfarande är NP-hårda, faktiskt #P-kompletterade, i mycket begränsade klasser av grafer. I synnerhet, Det visas att problemen med att räkna matchningar, vertex täcker, oberoende uppsättningar, och extrem varianter av dessa alla förblir svårt när begränsas till planar bipartit grafer av begränsad grad eller regelbundna grafer av konstant grad. För att uppnå dessa resultat införs en ny interpolationbaserad reduktionsteknik som bevarar egenskaper som konstant grad. Dessutom, problemet med ungefär räkna minimal kardinality vertex täcker visas vara NP-hård även när begränsas till grafer av maximal grad 3. Tidigare, begränsade fall komplexa resultat för att räkna problem var svårfångade; vi tror att våra tekniker kan bidra till att få liknande resultat för många andra räkna problem.
Några av dessa resultat utvidgades senare av Vadhan till ännu mer begränsade bipartit grafer av begränsad grad REF.
The Complexity of Counting in Sparse, Regular, and Planar Graphs
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}