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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.