Directed Ear Anonymity

We define and study a new structural parameter for directed graphs, which we call \emph{ear anonymity}. Our parameter aims to generalize the useful properties of \emph{funnels} to larger digraph classes. In particular, funnels are exactly the acyclic digraphs with ear anonymity one. We prove that computing the ear anonymity of a digraph is \NP/-hard and that it can be solved in $O(m(n+m))$-time on acyclic digraphs (where $n$ is the number of vertices and $m$ is the number of arcs in the input digraph). It remains open where exactly in the polynomial hierarchy the problem of computing ear anonymity lies, however for a related problem we manage to show ${\mathrm{\Sigma }}_2^p$-completeness.