Computational complexity of list coloring and ıts variants for particular graph classes
Liste renklendirme probleminin ve varyantlarının belirli çizge sınıfları için hesaplama karmaşıklığı
Yazar: BANU BAKLAN ŞEN
Danışman: DR. ÖĞR. ÜYESİ ÖZNUR YAŞAR DİNER
Kadir Has Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Bilim ve Teknoloji = Science and Technology ; Matematik = Mathematics

Özet:
Her bir 𝑣 ∈ 𝑉 düğümü için bir 𝐺 = (𝑉, 𝐸) çizgesi ve her bir düğüme atanan mevcut renklerin bir listesi 𝐿(𝑣) verilmiştir. Burada Liste 3-Renklendirme problemi her düğümün 𝐿(𝑣) ⊆ {1, 2, . . . , 𝑘}, kendi listesinden bir renk aldığı ve 𝐺'deki hiçbir iki komşu düğümün aynı rengi alamadığı renk atama problemini ifade eder. Liste 3-Renklendirme probleminin karar versiyonu, iki parçalı çizgeler için NP-Tamdır ve tarak dışbükey iki parçalı çizgelerdeki karmaşıklığı açık bir problemdir. Bu tezde Liste 3-Renklendirme problemini tarak dışbükey iki parçalı çizgelerin süper sınıfı olan tırtıl dışbükey iki parçalı çizgelere indirgeyen polinom zamanlı bir algoritma veriyoruz. Tanıma algoritmaları verimli algoritmaların tasarlanmasında çok önemli bir yer tutar. İki parçalı çizgeler gibi birçok çizge sınıfını tanımak ve bir çizgenin uygun temsilini üretmek için iyi bilinen algoritmalar vardır. Burada tırtıl dış bükey iki parçalı çizge sınıfı için bir polinom zamanlı tanıma algoritması ve bu çizgeye karşılık gelen bir tırtıl temsili veriyoruz. Bu algoritma değiştirilerek, tarak dışbükey iki parçalı çizgelerin için bir polinom zamanlı tanıma algoritması verildi. Liste 3-Renklendirme ve tanıma algoritmalarının yanında Liste renklendirme probleminin bir uygulaması olan Futoshiki Problemi ile ilgileniyoruz. Futoshiki, bir NP-Tam Latin Kare Tamamlama Tipi Bulmacasıdır. Futoshiki bulmacasını bir koşul tatmin problemi olarak ele aldığımızda, öncelikle buna yönelik bir liste renklendirme tabanlı algoritma veriyoruz. Ayrıca, geliştirdiğimiz algoritmanın performansını gerçekleştirdiğimiz deneylerden elde ettiğimiz sonuçlarla karşılaştırmak için iki deterministik algoritma daha sunuyoruz. Son olarak, Minimum Çatışma Algoritması, Karınca Kolonisi Optimizasyon Algoritması ve Genetik Algoritmayı içeren üç stokastik algoritma veriyoruz.

Abstract:
Given a graph 𝐺 = (𝑉, 𝐸) and a list of available colors 𝐿(𝑣) for each vertex 𝑣 ∈ 𝑉, where
𝐿(𝑣) ⊆ {1, 2, . . . , 𝑘}, List 𝑘-Coloring refers to the problem of assigning colors to the vertices
of 𝐺 so that each vertex receives a color from its own list and no two neighboring vertices
receive the same color. The decision version of the problem, List 3-Coloring, is NP-complete
even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open
problem. In this thesis, we give a polynomial-time algorithm to solve List 3-Coloring for
caterpillar-convex bipartite graphs, a super class of comb-convex bipartite graphs. Recognition
algorithms are crucial in designing efficient algorithms. There are well-known algorithms for
recognizing particular graph classes such as, bipartite graphs, and producing a corresponding
representation for it. On the other hand, finding an efficient recognition algorithm gets harder
as the graph class gets complex. Here we give a polynomial-time recognition algorithm for
the class of caterpillar-convex bipartite graphs and give a caterpillar representation for it. This
algorithm is further modified to give a polynomial-time recognition algorithm for a subclass
of comb-convex bipartite graphs. As an application of list coloring problem we are interested
in the Futoshiki Problem. Futoshiki is an NP-complete Latin Square Completion Type Puzzle.
Considering Futoshiki puzzle as a constraint satisfaction problem, we first, give a list coloring
based algorithm for it. Then we give two additional deterministic algorithms to compare its
performance by computational experiments. Finally, we give algorithms that employ stochastic
approaches including a Minimum Conflicts Algorithm, an Ant Colony Optimization Algorithm,
and a Genetic Algorithm.