I denna artikel studerar vi den parameteriserade komplexiteten av problem som består i att hitta grad-konstruerade subgrafer, tar som parameter antalet hörn av den önskade subgrafen. Nämligen, givet två positiva heltal d och k, studerar vi problemet med att hitta en d-regelbunden (inducerad eller inte) subgraph med som mest k hörn och problemet med att hitta en subgraph med som mest k hörn och av minimum grad minst d. Det senare problemet är en naturlig parameterisering av d-cirrth av en graf (den minsta ordningen av en inducerad subgraph av minimum grad åtminstone d). Vi visar först att båda problemen är fasta-parameter intractable i allmänna grafer. Mer exakt visar vi att det första problemet är W [1]-hård med hjälp av en minskning från MultiColor Clique. Hårdheten i det andra problemet följer av en enkel förlängning av ett redan känt resultat. Vi tillhandahåller sedan explicita fasta-parameterdragbara (FPT) algoritmer för att lösa både problem i grafer med avgränsad lokal trädbredd och grafer med uteslutna minderåriga, med hjälp av en dynamisk programmering. Även om dessa problem lätt kan definieras i första ordningens logik, alltså genom resultaten av Frick och Grohe [23] är FPT i grafer med avgränsad lokal trädbredd och grafer med uteslutna minderåriga, beroendet av k av våra algoritmer är betydligt bättre än den följande från [23].
Den parameteriserade komplexiteten hos vissa relaterade problem anges i REF.
Parameterized complexity of finding small degree-constrained subgraphs
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}