On Disjoint Total Dominating Sets and Sorting from Partial Information - Graph Theory and Graph Algorithms

Comparison based sorting is a well understood problem. There are many algorithms that sort n elements in O(n log n) comparisons, and this is tight since log2(n!) ∈ Ω(n log n). So what if you already know that some elements are smaller than others. Can you then do better? If there are e(P) sorted orders (permutations) compatible with the information P you already know, then any algorithm needs to do Ω(log e(P)) comparisons. The problem of Sorting from Partial Information is to match this bound, i.e. design an efficient algorithm that preprocesses P and sorts in O(log e(P)) comparisons. We also discuss how different representations of P affect the preprocessing time.

Given an undirected graph, can you color all vertices red or blue such that every vertex has a red and a blue neighbor? This is precisely the problem of finding two disjoint total dominating set, corresponding to each color class. In general, it is NP hard to find such a coloring, but for certain graph classes, the problem is tractable. We show that such a coloring always exists for planar graphs of minimum degree degree ≥ 3, and classify the 2-connected cubic graphs with no such coloring.