Abstrakt. Eftersom en oriktad graf G = (V, E) och ett heltal ≥ 1, den NP-hard 2-Club problemet ber om en vertex uppsättning S  och V av storlek åtminstone sådan att den subgraph induceras av S har diameter som mest två. I detta arbete utökar vi tidigare parameteriserade komplexitetsstudier för 2-Club. På den positiva sidan ger vi polynomkärnor för parametrarna "feedback edge set size of G" och "size of a cluster redigering set of G" och presentera en direkt kombinatorial algoritm för parametern "treewidth of G". På den negativa sidan visar vi först att om inte NP  ska coNP/poly, 2-Club inte medger en polynom kärna med avseende på "storleken på en vertex omslag av G". Därefter visar vi att, under den starka exponentiella tidshypotesen, en tidigare O * (2  och V) sökträdsalgoritm [Schäfer et al., Optim. Lått. 2012] kan inte förbättras och att det inte finns någon polynomkärna för den dubbla parametern. Slutligen visar vi att, trots denna lägre gräns, sökträdsalgoritmen för den dubbla parametern  på V kan ställas in i en effektiv exakt algoritm för 2-Club som avsevärt överträffar tidigare implementationer.
I följeslagare arbete REF, Vi övervägde olika strukturella parametrar: Vi presenterade en fast-parameter algoritm för parametern trädbredd och polynom kärnor för parametrarna (storlek på a) feedback edge set och kluster redigeringsnummer.
Parameterized algorithmics and computational experiments for finding 2-clubs
{'venue': 'In Proc. 7th IPEC, volume 7535 of LNCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}