Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Hauptinhalt

Effiziente Algorithmen für Probleme auf implizit, insbesondere durch BDDs beschriebenen Netzwerken

Ein Projekt im Rahmen des DFG-Schwerpunktes 1126, "Algorithmik großer und komplexer Netzwerke".


Bekannte Algorithmen zur Behandlung von Netzwerkproblemen stoßen bei großen Netzwerken an ihre Grenze. Dann können selbst Rechenzeiten, die Polynome kleinen Grades sind, zu groß sein. Darüber hinaus führt die Modellierung technischer Systeme, des Verkehrs und auch des WWW zu so großen Netzwerken, dass diese nicht mehr explizit, also durch Auflistung aller Knoten und Kanten beschreibbar sind. Alternative Beschreibungsformen, in denen weder die Knoten noch die Kanten explizit genannt werden, heißen implizit. Die Behandlung der zentralen algorithmischen Probleme auf implizit beschriebenen Netzwerken stellt eine neue Herausforderung dar. Für zentrale Module von Netzwerkalgorithmen sollen BDD-basierte Algorithmen ebenso entwickelt, implementiert und analysiert werden wie für umfassende Netzwerkprobleme. Hierbei sollen Paradigmen für diesen neuen Algorithmentyp entstehen und mit Paradigmen für verwandte Algorithmenklassen verglichen werden.

Das Thema des Schwerpunktprogramms umfasst die Algorithmik großer und komplexer Netzwerke. In diesem Teilprojekt sollen sehr große, aber nicht beliebig komplexe Netzwerke algorithmisch behandelt werden. Sehr große Netzwerke müssen Strukturen aufweisen, um überhaupt effizient beschreibbar zu sein. Die Knotenmenge kann sich beispielsweise als Kreuzprodukt $V_1 \times \cdots \times V_k$ so strukturieren lassen, dass die Kantenrelation stets nur von wenigen Komponenten des Produkts abhängt oder die Beziehung innerhalb der Komponenten einfach ist. Wenn eine Komponente die Zeit $t$ darstellt, gibt es vielleicht nur Kanten von Knoten $u$ mit Zeitpunkt $t$ zu Knoten $v$ mit Zeitpunkt ${t+1}$. Sehr große Netzwerke sind bisher vor allem in den Bereichen Verifikation, Hardwareentwurf, CAD und Model Checking behandelt worden. Rechnerkomponenten lassen sich durch Zustandsüberführungsgraphen beschreiben. Selbst bei Rechnerkomponenten kleiner Größe (in der Darstellung als sequentieller Schaltkreis) kann die explizite Beschreibung des Zustandsgraphen praktisch unmöglich sein. Dass BDD-Darstellungen für viele Anwendungsprobleme in diesen Gebieten erfolgversprechend sind, ist inzwischen allgemein bekannt.

Die Netzwerke in anderen Gebieten (Verkehrsprobleme, Klassifikation wie Clusterbildung, WWW, ...) werden immer größer, so dass die im Hardwarebereich bewährten Methoden auch in diesen Gebieten Anwendung finden sollten. Eine einfache und direkte übertragung der Methoden ist jedoch nicht möglich. Einerseits hat man es in den neuen Gebieten mit ganz anderen Charakteristika von Netzwerken zu tun und andererseits auch mit anderen algorithmischen Problemstellungen.


Arbeitsgruppe


Ziele und Arbeitsprogramm

Im Mittelpunkt stehen Entwurf, Analyse und Implementierung impliziter Netzwerkalgorithmen. Die dabei betrachteten Probleme können aus Sicht expliziter Algorithmen bereits gelöst sein, z.B. durch auch praktisch effiziente Linearzeit-Algorithmen. Eine direkte übertragung auf durch OBDDs dargestellte Netzwerke mag zwar prinzipiell möglich sein (naiv durch Umwandlung der OBDD-Darstellung in eine Adjazenzmatrix), aber diese Vorgehensweise nutzt nicht das Potenzial der OBDD-Darstellung aus. Wenn die Netzwerke dann bzgl. der expliziten Darstellung eine sublineare, eventuell gar polylogarithmische Darstellungsgröße haben, besteht die Hoffnung, auch insgesamt mit einer sublinearen Rechenzeit (bzgl. der Anzahl an Knoten und Kanten) auszukommen. Auf Grund der inhärenten Komplexität selbst einfacher Probleme wie Graphzusammenhang ist dieses Vorgehen selbst inhärent heuristisch; jedoch besteht die Möglichkeit, für Teilklassen von Netzwerken mit kleiner OBDD-Größe die Effizienz des Vorgehens auch nachzuweisen.

Insgesamt kann festgestellt werden, dass OBDD-basierte Netzwerkalgorithmen bereits in vielen konkreten Anwendungen benutzt werden, es aber weit weniger Arbeitsgruppen gibt, die diese Forschung mit einer Analyse des Ressourcenverbrauchs verbinden. In diesem Zusammenhang ist neben der Rechenzeit der benötigte Speicherplatz von Interesse, da viele OBDD-Anwendungen daran scheitern, dass die beteiligten OBDDs zu groß werden. Wir werden also den Entwurf impliziter Netzwerkalgorithmen weiterhin mit einer theoretischen Analyse begleiten. Als vergröberndes Maß für die Rechenzeit kann dabei die Anzahl der OBDD-Operationen verwendet werden. Im letzten Fall kann zwischen einfachen Operationen, die lineare Zeit bzgl. der OBDD-Größe benötigen, und komplexen Operationen wie der Synthese unterschieden werden. Es sind gerade die Syntheseschritte, die größere OBDDs erzeugen können. Ein symbolischer Schritt ("image-Operation") beinhaltet eine lineare Anzahl an Syntheseschritten bzgl. der Anzahl der Variablen. Letztere ist in allen bisher entstandenen OBDD-basierten Netzwerkalgorithmen logarithmisch in der Knotenanzahl und somit nicht kritisch für die Anzahl ausgeführter OBDD-Operationen. Obwohl unsere Vorgehensweise beim Zählen der Operationen genauer ist, sind die Ergebnisse mit denen über die Anzahl symbolischer Schritte vergleichbar und somit kein Alleinstellungsmerkmal.

Anders ist dies bei unserer erweiterten Analyse, bei der für einfache Netzwerke die Größe aller im Verlauf des Algorithmus konstruierten OBDDs abgeschätzt wird und damit auch Ergebnisse über die Anzahl der Gesamtrechenschritte ableitbar werden. Eine solche Analyse ist ungleich komplizierter und wurde nur in wenigen Arbeiten anderer durchgeführt, die aber in anderen Gebieten wie Verifikation und Kryptanalyse liegen. Es ist uns ein Anliegen, unsere Analysetechniken in dieser Richtung zu verfeinern. Offensichtlich können OBDD-basierte Netzwerkalgorithmen nur dann eine Alternative sein, wenn die entstehenden OBDDs kleine Größe haben. Es gibt prinzipielle Schranken dort, wo bestimmte Netzwerke (oder aber temporäre Berechnungsergebnisse) sehr große OBDDs erfordern. Implizite Verfahren versagen aber praktisch auch dann, wenn unnötig große OBDDs entstehen.

Ein weiterer Schwerpunkt unserer Arbeit wird es daher sein, Methoden zu entwickeln, mit denen es häufig gelingt, mit möglichst kleinen BDDs zu arbeiten. Optionen gibt es dabei nicht nur, wie bei OBDDs üblich, bei der Wahl einer geeigneten Variablenordnung, sondern auch bei der Wahl einer geeigneten Codierung der Knoten. Im zweiten Fall ist der Spielraum wesentlich größer. Bei $n=2^{k}$ Knoten gibt es $n!$ Knotencodierungen der Bitlänge $k$, bei der Netzwerkdarstellung mit $2k$ booleschen Variablen für die Bits zweier Knotennummern aber "nur" $(2k)!$ Variablenordnungen. Ein einfacher Pfad der Länge $n$ hat bei geeigneter Knotencodierung OBDD-Größe $O(\log n)$; andere Knotencodierungen können jedoch Größe $\Omega(n)$ erzwingen. Heuristiken zur Berechnung guter Knotencodierungen existieren bisher nicht.

Es gibt keinen prinzipiellen Grund, sich auf eine Darstellung durch OBDDs zu beschränken. Manche Alternativen (OKFDDs oder *BMDs) beziehen ihre Motivation vor allem aus anderen Anwendungsgebieten, andere wiederum (FBDDs oder IBDDs) haben im praktischen Einsatz gravierende Probleme, da nicht für alle gängigen Operationen polynomielle Algorithmen möglich sind (falls NP≠P). Die vielversprechendste Alternative stellen aus unserer Sicht partitioned OBDDs (POBDDs) dar. Ihr Einsatz soll untersucht werden.

Die bisherige Literatur wie auch unsere eigenen Arbeiten gehen davon aus, dass die betrachteten Netzwerke bereits in OBDD-Darstellung vorliegen. Sehr große, aber reguläre Netzwerke liegen typischerweise in zwar impliziter Darstellung vor, allerdings nicht als OBDD. Dies kann z.B. eine formale logische Beschreibung sein ("von Knoten $(v,t)$ führen Kanten zu allen Knoten $(v',t')$ mit $t'=t+1$ und $\vert v-v'\vert=2^{i}$ für $i \ge 0$"). Wir wollen unsere Ergebnisse ergänzen um Algorithmen zur übertragung derartiger Netzwerkbeschreibungen in OBDD-Darstellungen.

Es gibt zwar eine Reihe von Besonderheiten beim Entwurf OBDD-basierter Netzwerkalgorithmen, aber es ist natürlich sinnvoll zu untersuchen, welche zentralen Ideen beim Entwurf von Algorithmen unter anderen Nebenbedingungen auf das Szenario impliziter Netzwerkalgorithmen übertragen werden können. Sicherlich wurden schon Methoden aus dem Reservoir von Entwurfsmethoden verwendet (z.B. Breitensuche, iteratives Quadrieren und dynamische Programmierung). Wir sehen aber beim Entwurf paralleler, externer und OBDD-basierter Algorithmen verwandte Probleme. Es gibt jeweils einen Flaschenhals, in dem sequentielle Entscheidungen unmöglich sind. In einem parallelen Algorithmus müssen alle Prozessoren gleichzeitig arbeiten; d.h. $P_{i}$ kann seinen Rechenschritt nicht vom Ergebnis des gleichzeitigen Rechenschrittes von $P_{j}$ abhängig machen. Bei einem externen Algorithmus muss gleichzeitig viel sinnvolle Information vom externen in den internen Speicher transportiert werden. Ein guter Schritt in einem OBDD-basierten Algorithmus muss für viele Knoten/Kanten gleichzeitig sinnvoll sein. Da parallele und externe Algorithmen bisher intensiv untersucht wurden, ist zu analysieren, welche Ideen aus diesen Gebieten hilfreich beim Entwurf OBDD-basierter Netzwerkalgorithmen sind.

Zwei weitere Arbeitspakete sollen das Arbeitsprogramm abrunden. Es soll grundsätzlich untersucht werden, warum OBDD-basierte Algorithmen in vielen Anwendungen überhaupt erfolgreich sind. Im worst case führt schon eine kleine Folge von Syntheseoperationen zu einer Vergrößerung der beteiligten OBDDs, die praktisch einen Abbruch des Algorithmus nach sich zieht. Woran liegt es, dass häufig selbst eine große Anzahl von OBDD-Operationen nur OBDDs vertretbarer Größe erzeugt? Ein letztes Arbeitspaket hat nichts mit dem Ziel unseres Projektes zu tun, dient aber der Unterstützung eines anderen Projektes in diesem Schwerpunktprogramm.

Zusammengefasst ergeben sich die folgenden Arbeitspakete:

  1. Entwurf, Analyse und Implementierung OBDD-basierter Netzwerkalgorithmen
  2. POBDD-basierte Netzwerkalgorithmen
  3. OBDD-Techniken für Netzwerkalgorithmen
  4. Transformation von Netzwerkbeschreibungen in OBDD-basierte Darstellungen
  5. Eine vergleichende Betrachtung von Entwurfsmethoden bei Netzwerkalgorithmen
  6. Pseudozufällige OBDDs
  7. Selbstorganisierende Evolution von Netzwerken

Publikationen und Berichte

  • Bollig, B. (2005).
    Property Testing and the Branching Program Size of Boolean Functions.
    FCT'05, LNCS 3623, 258-269.
  • Bollig, B., Sauerhoff, M., Sieling, D. und Wegener, I. (2005).
    Binary Decision Diagrams.
    Erscheint in Boolean Functions Vol. II, Crama, Y. und Hammer, P. (Hrsg.).
  • Bollig, B. und Wegener, I. (2003).
    Functions that Have Read-Once Branching Programs of Quadratic Size Are not Necessarily Testable.
    Information Processing Letters 87, 25-29.
  • Nunkesser, M. und Sawitzki, D. (2005).
    Blockmodels.
    Kapitel 10 in Network Analysis, Brandes, U. und Erlebach, T. (Hrsg.), LNCS 3418, 253-292.
  • Nunkesser, R. und Woelfel, P. (2005).
    Representation of Graphs by OBDDs.
    ISAAC'05, LNCS 3827, 1132-1142.
  • Sawitzki, D. (2004).
    A Symbolic Approach to the All-Pairs Shortest-Paths Problem.
    WG'04, LNCS 3353, 154-167.
  • Sawitzki, D. (2004).
    Experimental Studies of Symbolic Shortest-Path Algorithms.
    WEA'04, LNCS 3059, 482-497.
  • Sawitzki, D. (2004).
    Implicit Flow Maximization by Iterative Squaring.
    SOFSEM'04, LNCS 2932, 301-313.
  • Sawitzki, D. (2004).
    Implicit Flow Maximization on Grid Networks.
    Technischer Bericht, Universität Dortmund.
  • Sawitzki, D. (2004).
    Implicit Maximization of Flows over Time.
    Technischer Bericht, Universität Dortmund.
  • Sawitzki, D. (2004).
    On Graphs with Characteristic Bounded-Width Functions.
    Technischer Bericht, Universität Dortmund.
  • Sawitzki, D. (2005).
    Lower Bounds on the OBDD Size of Graphs of Some Popular Functions.
    SOFSEM'05, LNCS 3381, 298-309.
  • Sawitzki, D. (2005).
    On Symbolic Scheduling Independent Tasks with Restricted Execution Times.
    WEA'05, LNCS 3503, 277-289.
  • Sawitzki, D. (2006).
    Algorithmik und Komplexität OBDD-repräsentierter Graphen.
    Dissertation, Universität Dortmund.
  • Sawitzki, D. (2006).
    Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms.
    LATIN 2006, LNCS 3887, Springer, 781-792.
  • Sawitzki, D. (2006).
    The Complexity of Problems on Implicitly Represented Inputs.
    SOFSEM'06, LNCS 3831, 471-482.
  • Sawitzki, D. (2007).
    Implicit Simulation of FNC Algorithms.
    ECCC Report TR07-028.
  • Sawitzki, D. (2007).
    Lower Bounds on the OBDD Size of Two Fundamental Functions' Graphs.
    IPL 101, 66-71.
  • Wegener, I. (2004).
    BDDs - Design, Analysis, Complexity, and Applications.
    Discrete Applied Mathematics 138, 229-251.
  • Wegener, I. und Woelfel, P. (2005).
    New Results on the Complexity of the Middle Bit of Multiplication.
    CCC'05, 100-110.
  • Woelfel, P. (2003).
    Symbolic Topological Sorting with OBDDs.
    Erscheint in Journal of Discrete Algorithms.
    (Vorabversion erschien in MFCS'03, LNCS 2747, 671-680.)

Vorträge

  • Algorithms on Implicit Networks.
    Gehalten auf dem Jahreskolloquium des DFG-Schwerpunkts 1126, "Algorithmik großer und komplexer Netzwerke", am 26.-28. März 2003 an der Universität Tübingen.
    PDF (4.131K)
  • Implicit Flow Maximization by Iterative Squaring.
    Gehalten auf der SOFSEM 2004 am 24.-30. Januar 2004 im Hotel VZ Merin, Merin, Tschechien.
    PDF (5.972K)
  • Experimental Studies of Symbolic Shortest-Path Algorithms.
    Gehalten auf dem WEA 2004 am 25.-28. Mai 2004 im Hotel Portogalo, Angra dos Reis, Rio de Janeiro, Brasilien.
    PDF (768K)
  • A Symbolic Approach to the All-Pairs Shortest-Paths Problem.
    Gehalten auf dem WG 2004 am 21.-23. Juni 2004 im Hölterhoff Haus, Bad Honnef.
    PDF (616K)
  • Symbolische Berechnung kürzester Wege.
    Gehalten am Lehrstuhl Informatik 2 der Universität Dortmund am 13. Juli 2004.
    PDF (893K)
  • Symbolische Berechnung kürzester Wege.
    Gehalten auf dem Jahreskolloquium des DFG-Schwerpunkts 1126, "Algorithmik großer und komplexer Netzwerke", am 21.-23. Juli 2004 an der Universität Karlsruhe.
    PDF (782K)

  • Lower Bounds on the OBDD Size of Graphs of Some Popular Functions.
    Gehalten auf der SOFSEM 2005 am 22.-28. Januar 2005 im Hotel MAJ, Liptovsky Jan, Slovakien.
    PDF (371K)

  • New Results on the OBDD-Size of Graphs.
    Gehalten auf dem Jahreskolloquium des DFG-Schwerpunkts 1126, "Algorithmik großer und komplexer Netzwerke", am 10.-12. März 2005 am Heinz Nixdorf Institut, Paderborn.
    PDF (382K)
  • On Symbolic Scheduling Independent Tasks with Restricted Execution Times.
    Gehalten auf dem WEA 2005 am 10.-13. May 2005 im Hotel Santorini Image, Santorini, Griechenland.
    PDF (407K)
  • Algorithmik implizit repräsentierter Graphen.
    Gehalten am Institut für Informatik und Praktische Mathematik der Universität Kiel am 26. Oktober 2005.
    PDF (824K)
  • The Complexity of Problems on Implicitly Represented Inputs.
    Gehalten auf der SOFSEM 2006 am 22.-27. Januar 2006 im Hotel VZ Merin, Merin, Tschechien.
    PDF (443K)
  • Die Komplexität von Problemen auf implizit repräsentierten Eingaben.
    Gehalten am Lehrstuhl Informatik 2 der Universität Dortmund am 7. Februar 2006.
    PDF (821K)
  • Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms.
    Gehalten auf der LATIN 2006 am 20.-24. März 2006 im Hotel Villa del Rio, Valdivia, Chile.
    PDF (259K)
  • The Complexity of Problems on Implictly Represented Inputs.
    Gehalten auf dem Jahreskolloquium des DFG-Schwerpunkts 1126, "Algorithmik großer und komplexer Netzwerke", am 12.-14. Juni 2006 an der RWTH Aachen.
    PDF (393K)

Software

  • The Figaro - The Framework for Implicit Graph Algorithms and Representations by OBDDs.
    Das "Framework for Implicit Graph Algorithms and Representations by OBDDs" (Figaro) ist ein Rahmensystem zur komfortablen Durchführung von algorithmischen Experimenten. Sowohl Generatoren für Eingabeinstanzen als auch Algorithmen werden als Plugin implementiert und eingebunden. Das Paket umfasst bereits Generatoren für verschiedene Netzwerke in expliziter und impliziter Darstellung. Weiterhin sind bereits explizite und implizite Netzwerkalgorithmen zur Flussmaximierung und zur Berechnung kürzester Wege enthalten.
    Sourceforge Projektseite

André Gronemeier, 1.3.2007