Exact algorithms for graph-theoretic frequency assignment problems

Wiele problemów napotykanych w przemyśle czy biznesie daje się w naturalny sposób modelować za pomocą grafów.Jednym z takich problemów jest problem przydziału częstotliwości. Polega on na takim przypisaniu kanałów częstotliwości nadajnikom sieci radiowej, aby uniknąć zakłóceń w nadawaniu sygnału. W zależności od tego, jak zdefiniujemy zakłócenia (i, co za tym idzie, konflikty między nadajnikami), możemy otrzymać wiele znanych problemów grafowych.Na przykład etykietowanie L(2,1) grafu G to przypisanie wierzchołkom $G$ nieujemnych liczb całkowitych w taki sposób, że etykiety sąsiadujących wierzchołków różnią się o co najmniej 2, zaś etykiety wierzchołków o wspólnym sąsiedzie są różne. Rozpiętością takiego etykietowania jest number największej użytej etykiety. Problem etykietowania L(2,1) polega na znalezieniu najmniejszej możliwej rozpiętości etykietowania L(2,1) grafu.Inne problemy rozważane w tym kontekście to: kolorowanie grafów, problem przydziału kanałów częstotliwości (ang. channel assignment problem), problem T-kolorowania itp.Ponieważ wszystkie wspomniane problemy są NP-trudne, szanse na znalezienie ich dokładnych rozwiązań w czasie wielomianowym są niewielkie.Dlatego w niniejszej pracy zajmujemy się projektowaniem algorytmów dokładnych o złożonościach ograniczonych pewną wykładniczą funkcją rozmiaru zadania.Opisujemy ogólną metodę, która może zostać zastosowana do rozwiązania pewnego typu problemów etykietowania grafów.Dokładniej, prezentujemy algorytm rozwiązujący problem tzw. uogólnionego listowego T-kolorowania (ang. generalized list T-coloring problem), będący wspólnym uogólnieniem wszystkich problemów wymienionych powyżej. Pokazujemy również, jak zmienia się złożoność algorytmu dla grafów o pewnej określonej strukturze.Następnie pokazujemy ulepszoną wersję tego algorytmu działającą dla problemu L(2,1)-etykietowania grafów. Złożoność obliczeniowa i pamięciowa naszego algorytmu wynosi O(2.6488^n).Ponadto, pokazujemy jak zmodyfikować ogólny algorytm, by otrzymać algorytmy weryfikujące istnieje homomorfizmu i lokalnie różnowartościowego homomorfizmu (ang. locally injective homomorphism) grafu G w graf H. Złożoność obliczeniowa i pamięciowa obu tych algorytmów wynosi O^*((b+2)^n), gdzie b oznacza bandwidth dopełnienia grafu H.Używając innej metody, konstruujemy algorytm dokładny dla problemu etykietowania L(2,1), działający w czasie O(7.4920^n) i pamięci wielomianowej. Następnie pokazujemy pewną modyfikację tej metody pozwalającą odpowiedzieć na pytanie, czy dany graf ma etykietowanie L(2,1) o rozpiętości co najwyżej k (gdzie k jest stałą). To podejście jest bardziej efektywne niż ogólny algorytm dla k <= 31.Szacowanie złożoności dokładnych algorytmów wykładniczych często wymaga rozwiązania pewnych problemów teorii grafów ekstremalnych.W naszym przypadku, pokazujemy górne i dolne ograniczenia na maksymalną liczbę zbiorów 2-niezależnych w grafie (czyli zbiorów niezależnych w kwadracie grafu) oraz innych, powiązanych, obiektów kombinatorycznych.

Many real-life problems have very natural graph-theoretic models. One of such problems is the frequency assignment problem. It asks for an assignment of channels of frequency to transmitters in a broadcast network, so that no pair of transmitters interfere with each other. Depending on a way how we define the interference, this leads to many well-studied graph theoretic problems.For example, an L(2,1)-labeling of a graph $G$ is a mapping from the vertex set of $G$ to the set of non-negative integers, such that the labels assigned to adjacent vertices differ by at least 2 and labels assigned to vertices with a common neighbor are different. The span of such a labeling is the maximum label used and the L(2,1)-labeling problem asks for the minimum span of an L(2,1)-labeling of G.Other models considered in this context are the graph coloring problem, the channel assignment problem, the T-coloring problem etc.Since all the problems mentioned above are NP-hard, there is little hope to solve them exactly in a polynomial time.Thus in this dissertation we are mostly interested in designing exact algorithms, whose complexities are bounded by exponential functions of the size of the input.We describe and analyze a general framework, which can be used to solve some type of graph labeling problems.More precisely, we design an algorithm, which solves the so-called generalized list T-coloring problem, which is a common generalization of all the problems mentioned above. We also show how to improve the complexity analysis if the input graph has some specific structure.Then we show how a refined version of this general algorithm works for the L(2,1)-labeling problem. The time and space complexity of our refined algorithm is O(2.6488^n).We also present how to adapt the general algorithm to obtain algorithms determining the existence of a homomorphism and a locally injective homomorphism from a graph G to a graph H, both working in time and space O^*((b+2)^n), where b is the bandwidth of the complement of H.Using a different approach, we construct an exact exponential algorithm for the L(2,1)-labeling problem, working in time O(7.4920^n) and using only polynomial space. We also modify this algorithm to determine if the input graph has an L(2,1)-labeling with the span at most k (for a constant k). This approach proves significantly better than the basic algorithm for k <= 31.Estimating time complexities of exact exponential algorithms often requires solving some problems from extremal graph theory.In our case, we give some upper and lower bounds for the maximum number of 2-packings in a graph (i.e. independent sets in a square of the graph) and some related graph-theoretic objects.