Disjunctive Queries of Safety in Graphs

Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices TVT\subseteq V, determine whether or not there is a path that does not visit any vertex in TT (i.e. you want to avoid all vertices in TT). Furthermore, in the disjunctive queries problem, you are given multiple safety objectives (i.e. multiple target sets TiT_i) and you are to determine whether or not there is a path where at least one of the safety objectives is satisfied (i.e. whether or not an infinite path avoids all vertices in at least one of the target sets). Disjunctive queries coincide with disjunctive objectives on graphs.

Parameters

  • nn: number of vertices
  • mm: number of edges
  • MECMEC: O(\min(n^2, m^{1.5}))

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table