Skip to content

Instantly share code, notes, and snippets.

@realazthat realazthat/minimizedag.md Secret
Last active Dec 26, 2015

Embed
What would you like to do?
MinimizeDAG2

##First, the Question: Minimal size of contracting a DAG into a new DAG

We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:

  1. Only nodes with the same number can be contracted into the same new node. $F(x) \neq F(y) \Rightarrow x' \neq y'$. (However, $x' \neq y'\nRightarrow F(x) \neq F(y)$.)
  1. We add all the old edges between new nodes: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$.
  2. This new graph is still a DAG.

What is the minimal $|V'|$? What is an algorithm creating a minimal new graph?


Intro: first I will reduce the Monotone 3SAT problem to our problem. Though the Monotone 3SAT problem is trivially satisfiable, our problem can further solve the Minimum True Monotone 3SAT problem, which is NP-hard; thus this problem is NP-hard.

###Reduction from Monotone 3SAT to our problem

We have a monotone boolean formula expressed as a sequence of variables, and a sequence of clauses. The cnf is of the form $\Phi = (\mathcal V,\mathcal C)$ such that:

$$\forall_{\left(c_i \in \mathcal C\right)} ~ \left.c_i=\left(x_j \vee x_k \vee x_l\right) \vphantom{\LARGE | } \right|_{\left(x_j,x_k,x_l \in \mathcal V\right)}$$ and

$$\left.{\Large{\bigwedge}}{i=1}^{n}{c_i}\right|{\genfrac{}{}{0}{}{c_i\in \mathcal C,}{n=\left|\mathcal C\right|}}.$$

####Conversion

We construct a graph, $G'=V',E'$. Each vertex in $G'$ has a label; vertices with the same label are eligible for contraction.

First we construct the graph as follows: for each $x_i \in \mathcal V$, we make two nodes, each labeled $x_i$, and a directed edge from one to the other.

enter image description here

(full view)

These nodes can of course be contracted, because they have the same label. We will consider variable/nodes that are contracted to be valued as false, and those that are uncontracted to be valued as true:

enter image description here

(full view)

After this step, $V'$ should contain $2\cdot \left|\mathcal V\right|$ nodes. Next, we introduce the clause constraints. For each clause, $c_i \in \mathcal C, ~ \left.c_i = (x_j \vee x_k \vee x_l) \right|_{x_j,x_k,x_l \in \mathcal V}$, we introduce one node $c_i$, and the following edges:

enter image description here

Note the duplicatation of $c_i$ is for viewing purposes only; there is only $1$ node labeled $c_i$. (full view)

After this step, we should have $2\cdot \left|\mathcal V\right| + |\mathcal C|$ nodes.

Now, if $x_i$, $x_j$ and $x_k$ get contracted, $c_i \rightarrow c_i$ will result in a cycle.

Here is another visualization, unrolling the clause constraint:

enter image description here

(full view)

Thus, each clause constraint requires that at least one of the variables it contains remain uncontracted; since the uncontracted nodes are valued as true, this requires that one of the variables be true; exactly what Monotone SAT requires for its clauses.

###Reduction from Minimum True Monotone 3SAT

Monotone 3SAT is trivially satisfiable; you can simply set all the variables to true.

However, since our DAG minimization problem is to find the most contractions, this translates to finding the satisfying assignment that produces the most false variables in our CNF; which is the same as finding the minimum true variables. This problem is sometimes called Minimum True Monotone 3SAT or here (as an optimization problem, or decision problem), or k-True Monotone 2SAT (as a weaker decision problem); both NP-hard problems. Thus our problem is NP-hard.


References:

Graph sources:

\documentclass[tikz,border=10pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{matrix}
\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{shapes}
\usepackage{verbatim}
\usepackage{amsmath}
\begin{document}
\begin{tikzpicture}[]
\tikzset{vnode/.style={draw, fill=blue!25,circle}}
\tikzset{fnode/.style={draw, ultra thick, fill=blue!20,circle}}
\matrix (m)
[matrix of math nodes,
row sep=3em,column sep=4em,minimum width=2em,
ampersand replacement=\&,
nodes={anchor=center}]
{
\node[vnode] {x_1}; \& \& \node[vnode] {x_1}; \\
\node[vnode] {x_2}; \& \& \node[vnode] {x_2}; \\
\node[vnode] {x_3}; \& \& \node[vnode] {x_3}; \\
\&...\& \\
\node[vnode] {x_i}; \& \& \node[vnode] {x_i}; \\
\&...\& \\
\node[vnode] {x_n}; \& \& \node[vnode] {x_n}; \\
};
\path[ultra thick,-stealth]
(m-1-3) edge node [below] {} (m-1-1)
(m-2-3) edge node [right] {} (m-2-1)
(m-3-3) edge node [right] {} (m-3-1)
(m-5-3) edge node [right] {} (m-5-1)
(m-7-3) edge node [right] {} (m-7-1)
;
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=2em]m-1-1.north west) -- ([yshift=2em]m-1-3.north east)
node[midway, above, font=\footnotesize, yshift=2em] {Nodes representing variables};
\end{tikzpicture}
\begin{tikzpicture}[]
\tikzset{vnode/.style={draw, fill=blue!25,circle}}
\tikzset{fnode/.style={draw, ultra thick, fill=blue!20,circle}}
\matrix (m)
[matrix of math nodes,
row sep=3em,column sep=4em,minimum width=2em,
ampersand replacement=\&,
nodes={anchor=center}]
{
\node[vnode] {x_1}; \& \& \node[vnode] {x_1}; \\
\node[vnode] {x_2}; \& \& \node[vnode] {x_2}; \\
\node[vnode] {x_3}; \& \& \node[vnode] {x_3}; \\
\&...\& \\
\node[vnode] {x_i}; \& \& \node[vnode] {x_i}; \\
\&...\& \\
\node[vnode] {x_n}; \& \& \node[vnode] {x_n}; \\
};
\path[ultra thick,-stealth]
(m-1-3) edge node [below] {} (m-1-1)
(m-2-3) edge node [right] {} (m-2-1)
(m-3-3) edge node [right] {} (m-3-1)
(m-5-3) edge node [right] {} (m-5-1)
(m-7-3) edge node [right] {} (m-7-1)
;
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=2em]m-1-1.north west) -- ([yshift=2em]m-1-3.north east)
node[midway, above, font=\footnotesize, yshift=2em] {Nodes representing variables};
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=-1em]m-5-3.west) -- ([yshift=-1em]m-5-1.east)
node[midway, below, font=\footnotesize, yshift=0]
{If this edge is contracted,\\
you will consider $x_i = \mathcal F$,\\
else, $x_i=\mathcal T$.};
\end{tikzpicture}
\begin{tikzpicture}[]
\tikzset{vnode/.style={draw, fill=blue!25,circle}}
\tikzset{fnode/.style={draw, ultra thick, fill=blue!20,circle}}
\matrix (m)
[matrix of math nodes,
row sep=3em,column sep=4em,minimum width=2em,
ampersand replacement=\&,
nodes={anchor=center}]
{
\node[fnode]{c_i};\&\node[vnode]{x_j};\&\&\node[vnode]{x_j};\\
\&\node[vnode]{x_k};\&\&\node[vnode]{x_k};\\
\phantom{c_i}\&\node[vnode] {x_l};\&\&\node[vnode]{x_l};\&\node[fnode]{c_i};\\
\& \&...\& \\
\\
};
\path[ultra thick,-stealth]
(m-1-4) edge node [below] {} (m-1-2)
(m-2-4) edge node [right] {} (m-2-2)
(m-3-4) edge node [right] {} (m-3-2)
(m-1-1) edge node [below] {} (m-1-2)
(m-1-4) edge node [below] {} (m-2-2)
(m-2-4) edge node [below] {} (m-3-2)
(m-3-4) edge node [below] {} (m-3-5)
;
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=2em]m-1-2.north west) -- ([yshift=2em]m-1-4.north east)
node[midway, above, font=\footnotesize, yshift=2em] {Nodes representing variables};
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([xshift=-2em]m-3-1.center) -- ([xshift=-2em]m-1-1.center)
node[midway, left, font=\footnotesize, xshift=-1em]
{Nodes representing clause\\
$c_i=\left(x_j,x_k,x_l\right)$. Note that\\
there is only one node labeled \\
$c_i$; for viewing ease, it is \\
repeated on both sides of the \\
graph, but in reality they are \\
the same node. The clause \\
consists of the additional node\\
and the additional edges linking\\
the variables together.};
\end{tikzpicture}
\begin{tikzpicture}[]
\tikzset{vnode/.style={draw, fill=blue!25,circle}}
\tikzset{fnode/.style={draw, ultra thick, fill=blue!20,circle}}
\matrix (mci)
[matrix of math nodes,
row sep=3em,column sep=4em,minimum width=2em,
ampersand replacement=\&,
nodes={anchor=center}]
{
\node[fnode] {c_i};
\& \node[vnode] {x_j};\& \node[vnode] {x_j};
\&\& \node[vnode] {x_k};\& \node[vnode] {x_k};
\&\& \node[vnode] {x_l};\& \node[vnode] {x_l};
\& \node[fnode] {c_i};\\
\\
};
\path[ultra thick,-stealth]
(mci-1-1) edge node [below] {} (mci-1-2)
(mci-1-3) edge node [below] {} (mci-1-2)
(mci-1-3) edge node [below] {} (mci-1-5)
(mci-1-6) edge node [below] {} (mci-1-5)
(mci-1-6) edge node [below] {} (mci-1-8)
(mci-1-9) edge node [below] {} (mci-1-8)
(mci-1-9) edge node [below] {} (mci-1-10)
;
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=2em]mci.north west) -- ([yshift=2em]mci.north east)
node[midway, above, font=\footnotesize, yshift=1em]
{Nodes representing clause $c_i=\left(x_j,x_k,x_l\right)$, unrolled
for viewing ease. Note that if all 3 edges would be contracted, \\
$c_i$ at the head would be able to reach $c_i$ at the foot; since
they are actually the same node, this would be a cycle. \\
Thus: one of the variables must remain uncontracted. Since an
uncontracted variable is valued as true, this implies \\
that at least one of the variables in the clause must be true. };
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=-2em]mci-1-3.west) -- ([yshift=-2em]mci-1-2.east)
node[midway, below, font=\footnotesize, yshift=-1em]
{Contracts if $x_j=\mathcal F$};
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=-2em]mci-1-6.west) -- ([yshift=-2em]mci-1-5.east)
node[midway, below, font=\footnotesize, yshift=-1em]
{Contracts if $x_k=\mathcal F$};
\draw [decorate,decoration={brace,amplitude=4pt},align=left]
([yshift=-2em]mci-1-9.west) -- ([yshift=-2em]mci-1-8.east)
node[midway, below, font=\footnotesize, yshift=-1em]
{Contracts if $x_l=\mathcal F$};
\end{tikzpicture}
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.