Analiza heurystyk dla problemu znajdowania drzewa rozpinającego o maksymalnej liczbie wierzchołków wewnętrznych

Dla danego grafu spójnego należy wyznaczyć drzewo rozpinające, którego liczba wierzchołków wewnętrznych (o stopniu co najmniej 2) jest maksymalna pośród wszystkich jego drzew rozpinających. Jest to uogólnienie problemu ścieżki Hamiltona, zatem udzielenie dokładnej odpowiedzi w czasie wielomianowym jest niemożliwe, zakładając że P!=NP. W niniejszej pracy w usystematyzowany sposób prezentujemy możliwe rozwiązania tego problemu: opublikowane algorytmy aproksymacyjne i heurezy przy użyciu algorytmów przeszukiwania grafu. Przedstawiamy randomizowaną wersję algorytmu przeszukiwania grafu oraz nowe reguły rozszerzające algorytm przeszukiwania przestrzeni alternatywnych rozwiązań. Pokazujemy wyniki eksperymentów przeprowadzonych na dwóch modelach grafów losowych oraz bibliotece rzeczywistych sieci komputerowych, używając własnej implementacji omawianych algorytmów, którą udostępniamy publicznie. Z eksperymentów płyną wnioski na temat użyteczności rozważanych rozwiązań i praktyczne wskazówki dla ich wykorzystania. Zaprezentowane tu po raz pierwszy algorytmy dają obiecujące wyniki, które mogą zainteresować także teoretyków – nowe reguły mają szansę poprawić współczynnik aproksymacji najlepszego znanego algorytmu.

The task is to find a spanning tree of a connected graph such that no other tree spanning it has more internal vertices (i.e., of degree at least 2). This is a generalization of the Hamiltonian Path problem, therefore an exact general solution must be prohibitively time consuming, unless P=NP. We give a systematic overview of inexact algorithms for this problem, including a survey of published approximation algorithms and heuristic solutions via graph traversal algorithms. We propose a randomized traversal algorithm and extend a local search algorithm with new rules. We present experimental results using two random graph models, a library of real world network instances, and our implementation of discussed algorithms, which we make publicly available. Experiments let us draw conclusions about the utility of each approach and make recommendations for practitioners. Algorithms proposed here show promising results even for theoreticians, particularly the new rules may potentially improve the best known approximation ratio for the problem.