Reliable Connectivity for Failures of Incoming Edges (RCIN)

Input

A directed acyclic graph $G = (V, E)$, and two distinguished vertices $s$ and $t$. Additionally, a function $f$ that assigns a nonnegative integer to every vertex $v \in V$ such that $f(v)$ is less than or equal to the indegree of $v$.

Problem

Is there a directed path between $s$ and $t$ consisting of edges that are not in $\bigcup\limits_{v \in V} F(v)$?

Definitions

A choice of failed edges for a vertex $v$ is denoted $F(v)$. It consists of a set of incoming edges to $v$ of cardinality less than or equal to $f(v)$.

Status

$\P$-complete (Kavadias, Kirousis, and Spirakis [1]).

Remarks

The reduction to show hardness is from MCVP. The general problem in which the input graph is not required to be a directed acyclic graph is $\coNP$-complete [1]. Kavadias, Kirousis, and Spirakis point out that the apparent reduction in complexity of RCIN is not due to the restriction to directed acyclic graphs but because of allowing only failures of in-edges [1]. They also show that approximating RCIN is $\P$-hard. They define another problem called Feasible Connectivity in which every vertex causes at least $f(v)$ edges to fail.

The question then is whether there exists at least one failure pattern in which there is a $s$ to $t$ path. This problem is in $\NC$ [1]. Kirousis and Spirakis define another problem called $\epsilon$Reliably Long Path [2]. In this problem exactly one of the arcs leading into a vertex fails; the goal is to compute the maximum number $k$ such that the directed acyclic graph has a path from the source vertex of length at least $k$ with probability one. They show that this problem is $\P$-complete [2].