DAG to $3$ CNF SAT

Question

Given a DAG G, how to reduce it to $3$ CNF SAT to prove it is NP Hard?.

Take a Directed Graph, instead of weighted we assign some alphabets to the edges. When we try to find a path from S to T, we consider the alphabets in the edges say ABEDA. So the cardinality(ABEDA) is 5. But A ia already recorded so we can ignore the last A, so the cardinality now is 4(ABED). Now the clear question,

Given the DAG, can we say that finding the path of cardinality k is NP-Hard?.

Note : This is a question to find a path $P$ from Source $S$ to Sink $V$ with cardinality $k$ or path value of atmost $K$. Proving NP wasn't so hard, since we can verify a path existence in $O(|V|*|E|)$ atmost time.

Answer 1

Note: The answer below refers to an earlier version of the question. Appropriate changes will be made in due course.

I don't think the problem is NP-hard, although you also need to be clearer about what the problem is, and you have the reduction the wrong way around (and the technicalities wrong).

There are two different basic problems you mention: (1) finding a path of length at most $k$ from source $s$ to sink $t$ in a directed acyclic graph (presumably unweighted, but it doesn't really matter) and (2) finding a path of exactly $k$ edges.

I'm not clear on what you mean by "cardinality" and "path value". Normally "cardinality" would mean the number of edges, and if I were forced to guess, "path value" would be the total weight of the edges in the path.

Regardless, all of these problems are solvable in polynomial time:

1. the shortest path problem is in P for general weighted graphs, so certainly is for DAGS (see for example the wikipedia page),
2. finding a path with $k$ edges in a DAG can be solved by dynamic programming (this answer can easily be adapted),
3. going even further longest path is also in P for DAGS, just in case you want paths of length at least $k$.

So you're probably not going to find an NP-hardness proof for these problems (if you do, you've just proved P = NP).

To address the other points, you can't reduce a DAG to 3-CNF SAT. A DAG is just a class of graphs, 3-CNF SAT is a problem. You reduced problems to other problems. As part of the reduction you map the input of one problem to the input of another. Furthermore, to prove NP-hardness, you need to reduce an NP-hard problem to the problem you're looking at (the idea being that if you could solve the new problem quickly, you could also solve the hard problem quickly).

So the question you should be asking is whether there is a reduction from 3-CNF SAT to your problem. This reduction would take a propositional formula in 3-CNF and construct a DAG such that the formula is satisfiable if and only if the DAG has an $st$-path of [length|weight] [at most|exactly|at least] (circle as applicable) $k$.

The final point is that $NP$, by definition, only contains decision problems, so you would technically have to phrase the problem as something like "Given a DAG $D$ with a source vertex $s$ and a sink vertex $t$, and integer $k$, does $D$ contain an $st$-path with exactly $k$ edges?". Note that this just asks a yes/no question, the output is not the path itself.