Für eine konstante , kann man in linearer Zeit, da ein Eingangs Graph bestimmen G , ob seine Baumweite IS ≤ k . Wenn jedoch sowohl k als auch G als Eingabe angegeben werden, ist das Problem NP-schwer. ( Quelle ).
Wenn der Eingabediagramm jedoch planar ist , scheint viel weniger über die Komplexität bekannt zu sein. Das Problem war anscheinend im Jahr 2010 offen , eine Behauptung, die auch in dieser Umfrage im Jahr 2007 und auf der Wikipedia-Seite für Branchenzerlegungen auftauchte . Umgekehrt wird das Problem in einer früheren Version der zuvor erwähnten Umfrage als NP-schwer (ohne Referenznachweis) bezeichnet , aber ich gehe davon aus, dass dies ein Fehler ist.
Ist es noch offen, die Komplexität des Problems zu bestimmen, wenn und ein planarer Graph G gegeben sind und G die Baumbreite ≤ k hat ? Wenn ja, wurde dies in einem kürzlich erschienenen Artikel behauptet? Sind teilweise Ergebnisse bekannt? Wenn nicht, wer hat es gelöst?
Antworten:
Soweit ich weiß, ist die NP-Vollständigkeit der Berechnung der Baumbreite eines planaren Graphen noch offen. Die letzte mir bekannte Referenz ist eine Umfrage von Bodlaender aus dem Jahr 2012 mit dem Titel "Fixed-Parameter Tractability of Treewidth and Pathwidth", die in der Festschrift zum 65. Geburtstag von Mike Fellows veröffentlicht wurde. Das Problem ist im Abschluss der Umfrage aufgeführt.
quelle