Pfadabdeckung

Pfadabdeckung bezeichnet in der Informatik das Ziel, durch eine Menge von Pfaden alle relevanten Elemente eines Objekts abzudecken. In der Graphentheorie wird der Begriff meist im Zusammenhang mit dem Pfadabdeckungsproblem verwendet: Ein Pfadabdeckung eines gerichteten Graphen G = (V,E) ist eine Menge von paarweise knoten-disjunkten Pfaden, so dass jeder Knoten von V genau in einem Pfad enthalten ist. Die Größe einer Pfadabdeckung ist die Anzahl der Pfade in der Menge. Das Minimum-Pfadabdeckungsproblem besteht darin, eine Abdeckung mit möglichst wenigen Pfaden zu finden.

Für gerichtete Acyclic Graphen (DAGs) lässt sich die Größe eines minimalen Pfadabdeckungs durch eine maximale Zuordnung in einem bipartiten Graphen bestimmen. Man bildet zwei Kopien jedes Knotens, eine linke und eine rechte, und erzeugt Kanten entsprechend den gerichteten Kanten des Originals. Die Größe des kleinsten Pfadabdeckungs wird dann zu |V| minus der Größe eines Maximum-Matchings. Allgemein gilt: Die Minimierung einer Pfadabdeckung in allgemeinen gerichteten Graphen ist NP-schwer; für DAGs lassen sich jedoch polynomialzeitige Algorithmen anwenden, typischerweise über Fluss- oder Matching-Verfahren.

Neben der graphtheoretischen Bedeutung bezeichnet der Begriff in der Softwaretechnik auch die Abdeckung von Ausführungspfaden eines Programms. Hier geht es darum, Testfälle zu entwerfen, die durch unterschiedliche Pfade des Kontrollflussgraphs (CFG) führen. Vollständige Pfadabdeckung ist oft unpraktisch wegen der Pfadexplosion; daher werden zusätzliche Abdeckungsgrade genutzt, wie Anweisungs-, Zweig- oder MCDC-Abdeckung, oder abstrakte Pfadklassen. Pfadabdeckung dient der Qualitätssicherung, dem Debugging und der Validierung von Compiler- oder Design-Optimierungen.