On a Game in Directed Graphs (Preprint)

Abstract

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no "nice" characterization of mortal graphs exists).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 16, 2002
Accession Number
ADA637901

Entities

People

  • Alan J. Hoffman
  • Kate Jenkins
  • Tim Roughgarden

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Computations
  • Computer Science
  • Computers
  • Elections
  • Governments
  • Information Operations
  • Information Processing
  • Mathematics
  • Polynomials
  • Probability
  • Sequences
  • Standards
  • Universities

Fields of Study

  • Mathematics

Readers

  • Game Theory.
  • Graph Algorithms and Convex Optimization.
  • Phased Array Antenna Design.