# Complexity of topological sorting with a special restriction

Let $$G = (V, E)$$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:

1. Input variable, with in-degree $$0$$ and out-degree $$\geqslant 1$$.
2. A gate, with in-degree $$2$$ and out-degree $$\geqslant 1$$.
3. Output variable, with in-degree $$1$$ and out-degree $$0$$.

Does there exist a polynomial-time algorithm, which finds the minimal natural number $$n$$ and a function $$f : V \rightarrow \{0, \cdots, n - 1\}$$, such that:

1. If $$v \rightarrow w$$ is an edge, $$f(v) < f(w)$$.
2. If $$f(v) = f(w)$$, there doesn't exist an $$u$$ such that $$u \rightarrow v$$ and $$u \rightarrow w$$ are edges.

We denote the minimal possible $$n$$ by $$M(G)$$.

Without condition 2, the minimal number $$n$$ can be acquired by topological sorting $$G$$ and compute the "rank" of each gate by $$\operatorname{rank}(u) = \max(\operatorname{rank}(v), \operatorname{rank}(w)) + 1$$, where $$v \rightarrow u, w \rightarrow u$$.

Without the restriction of every gate has in-degree $$\leqslant 2$$, the problem is NP-hard. Given an undirected graph $$H_0 = (V_0, E_0)$$, we can construct a DAG $$H_1 = (V_1, E_1)$$, where $$V_1 = V_0 \cup \{\alpha_e | e \in E_0\}$$, and add edges $$\alpha_e \rightarrow a, \alpha_e \rightarrow b$$ for each $$(a, b) \in E_0$$. Then, we can compute the chromatic number of $$H_0$$ by $$\chi(H_0) = M(H_1) - 1$$, and thus determine whether $$H_0$$ is 3-colorable.

However, if $$v \in H_0$$ has degree $$n$$, then $$v \in H_1$$ has in-degree $$n$$. With $$n \leq 2$$ for every vertex, the computation of $$\chi(H_0)$$ is not hard, because $$H_0$$ will contain only simple patterns (lines, circles).

I wonder if the problem is NP-hard with this constraint of vertex type; if it is, do we have some polynomial-time approximating alogrithm?