Search

A directed graph where there is exactly one edge between every pair of vertices is called a tournament. Finding the "best" set of vertices of a tournament is a well-studied problem in social choice theory. A tournament solution takes a tournament as input and outputs a subset of vertices of the input tournament. However, in many applications, for example, choosing the best set of drugs from a given set of drugs, the edges of the tournament are given only implicitly and knowing the orientation of an edge is costly. In such scenarios, we would like to know the best set of vertices (according to some tournament solution) by "querying" as few edges as possible. We, in this paper, precisely study this problem for commonly used tournament solutions: given an oracle access to the edges of a tournament T , find f (T) by querying as few edges as possible, for a tournament solution f. We first study some popular tournament solutions and show that any deterministic algorithm for finding the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and the top cycle must query Ω (n 2) edges in the worst case. We also show similar lower bounds on the expected query complexity of these tournament solutions by any randomized algorithm. On the positive side, we are able to circumvent our strong query complexity lower bound results by proving that, if the size of the top cycle of the input tournament is at most k , then we can find all the tournament solutions mentioned above by querying O (n k + n log ⁡ (n k) log ⁡ (k k − 1)) edges only. [ABSTRACT FROM AUTHOR]

The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set { 1 , ... , L }. They wake up at possibly different times and move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous algorithms. The time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. In most of the literature concerning rendezvous in graphs, the graph is finite and the time of rendezvous depends on its size. This approach is impractical for very large graphs and impossible for infinite graphs. For such graphs it is natural to design rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in infinite trees. All our algorithms work in finite trees as well. Our main goal is to study the impact of orientation of a tree on the time of rendezvous. We first design a rendezvous algorithm working for unoriented regular trees, whose time is in O (z (D) log ⁡ L) , where z (D) is the size of the ball of radius D , i.e., the number of nodes at distance at most D from a given node. The algorithm works for arbitrary delay between waking times of agents and does not require any initial information about parameters L or D. Its disadvantage is its complexity: z (D) is exponential in D for any degree d > 2 of the tree. We prove that this high complexity is inevitable: Ω (z (D)) turns out to be a lower bound on rendezvous time in unoriented regular trees, even for simultaneous start and even when agents know L and D. Then we turn attention to oriented trees. While for arbitrary delay between waking times of agents the lower bound Ω (z (D)) still holds, for simultaneous start the time of rendezvous can be dramatically shortened. We show that if agents know either a polynomial upper bound on L or a linear upper bound on D , then rendezvous can be accomplished in oriented trees in time O (D log ⁡ L) , which is optimal. If no such extra knowledge is available, a significant speedup is still possible: in this case we design an algorithm working in time O (D 2 + log 2 ⁡ L). [ABSTRACT FROM AUTHOR]

The Minimum Vertex Cover P roblem is the optimization problem of finding a vertex cover V c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this paper, we start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We study the new algorithm theoretically and empirically, and run simulations to compare its performance to that of some algorithms of a similar nature. [ABSTRACT FROM AUTHOR]