Discrete Mathematics, Algorithms and Applications

We give an efficient encoding and decoding scheme for computing a compact representation of a graph in one of unordered reduced trees, cographs and series-parallel graphs. The unordered reduced trees are rooted trees in which (i) the ordering of children of each vertex does not matter, and (ii) no vertex has exactly one child. This is one of basic models frequently used in many areas. Our algorithm computes a bit string of length 2ℓ – 1 for a given unordered reduced tree with ℓ ≥ 1 leaves in O(ℓ) time, whereas a known folklore algorithm computes a bit string of length 2n – 2 for an ordered tree with n vertices. Note that in an unordered reduced tree, ℓ ≤ n < 2ℓ holds. To the best of our knowledge this is the first of such a compact representation for unordered reduced trees. From the theoretical point of view, the length of the representation gives us an upper bound of the number of unordered reduced trees with ℓ leaves. Precisely, the number of unordered reduced trees with ℓ leaves is at most 2^2ℓ–2 for ℓ ≥ 1. Moreover, the encoding and decoding can be done in linear time. Therefore, from the practical point of view, our representation is also useful to store a lot of unordered reduced trees efficiently. We also apply the scheme for computing a compact representation to cographs and series-parallel graphs. We show that each of cographs with n vertices has a compact representation in 2n – 1 bits, and the number of cographs with n vertices is at most 2^2n–1. The resulting number is close to the number of cographs with n vertices obtained by the enumeration for small n that approximates Cdⁿ/n^3/2, where C = 0.4126⋯ and d = 3.5608⋯. Series-parallel graphs are well-investigated in the context of the graphs of bounded treewidth. We give a method to represent a series-parallel graph with m edges in ⌈2.5285m – 2⌉ bits. Hence the number of series-parallel graphs with m edges is at most 2^{⌈2.5285m–2⌉}. As far as the authors know, this is the first non-trivial result about the number of series-parallel graphs. The encoding and decoding of the cographs and series-parallel graphs also can be done in linear time.

A graph G is called a pairwise compatibility graph (PCG) if there exists a positive edge weighted tree T and two non-negative real numbers d_min and d_max such that each leaf l_u of T corresponds to a node u ∈ V and there is an edge (u, v) ∈ E if and only if d_min ≤ d_T (l_u, l_v) ≤ d_max, where d_T (l_u, l_v) is the sum of the weights of the edges on the unique path from l_u to l_v in T. In this paper we study the relations between the pairwise compatibility property and superclasses of threshold graphs, i.e., graphs where the neighborhoods of any couple of nodes either coincide or are included one into the other. Namely, we prove that some of these superclasses belong to the PCG class. Moreover, we tackle the problem of characterizing the class of graphs that are PCGs of a star, deducing that also these graphs are a generalization of threshold graphs.

Comparing and ranking information is an important topic in social and information sciences, and in particular on the web. Its objective is to measure the difference of the preferences of voters on a set of candidates and to compute a consensus ranking. Commonly, each voter provides a total order or a bucket order of all candidates, where bucket orders allow ties.

In this work we consider the generalization of total and bucket orders to partial orders and compare them by the nearest neighbor and the Hausdorff Kendall tau distances. For total and bucket orders these distances can be computed in time. We show that the computation of the nearest neighbor Kendall tau distance is NP-hard, 2-approximable and fixed-parameter tractable for a total and a partial order. The computation of the Hausdorff Kendall tau distance for a total and a partial order is shown to be coNP-hard.

The rank aggregation problem is known to be NP-complete for total and bucket orders, even for four voters and solvable in time for two voters. We show that it is NP-complete for two partial orders and the nearest neighbor Kendall tau distance. For the Hausdorff Kendall tau distance it is in , but not in NP or coNP unless NP = coNP, even for four voters.

The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT in I and an instance I' resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT to solve Π in I', either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. We use this setting to study weighted versions of MAX P_k-FREE SUBGRAPH and MAX PLANAR SUBGRAPH, which are representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. We also show that the techniques presented allow us to handle BIN PACKING.

Covers, being one of the most popular form of regularities in strings, have drawn much attention in the relevant literature. In this paper, we focus on the problem of linear-time inference of strings from cover arrays using the least sized alphabet. We present an algorithm that can reconstruct a string x over a binary alphabet whenever a valid cover array C is given as an input. We have devised our algorithm using several interesting combinatorial properties of cover arrays as well as an interesting relation between border array and cover array. Our algorithm runs in linear-time. The fact that, from any valid cover array, we can infer a binary string x, is, in itself, a fascinating result in stringology, and this work may be considered as the final step for this particular problem area.

We introduce a variant of fat heaps that does not rely on regular counters, and still achieves the optimal worst-case bounds: O(1) for find-min, insert and decrease, and O(log n) for delete and delete-min. Compared to the original, our variant is simpler to explain, more efficient, and easier to implement. Experimental results suggest that our implementation is superior to structures, like run-relaxed heaps, that achieve the same worst-case bounds, and competitive to structures, like Fibonacci heaps, that achieve the same bounds in the amortized sense.