Vi anser att problemet med att räkna, i en given graf, antalet inducerade k-vertex subgrafer som har ett jämnt antal kanter, och även det kompletterande problemet med att räkna k-vertex inducerade subgrafer med ett udda antal kanter. Vi visar att båda problemen är #W[1]-hårda när parameteriserade av k, i själva verket visar ett något starkare resultat om att räkna subgrafer med en egenskap som bara innehar för någon delmängd av k-vertex subgraphs som har ett jämnt (respektivt udda) antal kanter. Å andra sidan visar vi att problemen med att räkna jämna och udda k-vertex framkallade subgrafer båda erkänner en FPTRAS. Dessa approximationssystem bygger på ett överraskande strukturellt resultat, som utnyttjar idéer från Ramsey-teorin.
I REF hårdhet är etablerad för egenskapen att ha ett jämnt (eller udda) antal kanter, som subsumeras av Theorem 6.
The parameterised complexity of counting even and odd induced subgraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}