Abstrakt. Tree-Decompositions är hörnstenen i många dynamiska programmeringsalgoritmer för att lösa grafproblem. Eftersom komplexiteten hos sådana algoritmer i allmänhet beror exponentiellt på bredden (storleken på påsarna) av nedbrytningen, har mycket arbete ägnats åt att beräkna trädindelningar med liten bredd. Praktiska algoritmer som beräknar trädnedbrytningar finns dock bara för grafer med trädbredd mindre än 4. I sådana grafer domineras tidskomplexiteten hos dynamiska programmeringsalgoritmer baserade på trädnedbrytningar av storleken (antal påsar) på trädnedbrytningarna. Det är då intressant att försöka minimera storleken på träd-nedbrytningar. I detta utvidgade abstrakt, vi anser problemet med att beräkna en träd-nedbrytning av en graf med bredd som mest k och minsta storlek. Mer exakt, vi fokuserar på följande problem: med tanke på en fast k ≥ 1, vad är komplexiteten i att beräkna en träd-dekomposition av bredd som mest k med minsta storlek i klassen av grafer med trädbredd som mest k? Vi bevisar att problemet är NP-komplett för alla fasta k ≥ 4 och polynomial för k ≤ 2. Pågående arbete tyder också på att det är polynom för k = 3.
Det är känt att ett sådant problem är NP-komplett för varje fast k ≥ 4, det är polynom för k ≤ 2 och för k = 3 det är polynom för träd och 2-anslutna yttre planar grafer REF.
Minimum Size Tree-decompositions
{'venue': 'Electron. Notes Discret. Math.', 'journal': 'Electron. Notes Discret. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}