Computational complexity of list coloring and ıts variants for particular graph classes

Abstract

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.

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.