Number of implications needed

Question

I need some math directions since I'm lost.

Problem: I have $2$ values $n$ ($1 \le n \le 20000$) and $m$ ($0 \le m \le 50000$). $n$ is the number of statements and $m$ is the number of implications that have already been proved.

I also have $m$ pair of values $s_1$ and $s_2$ ($1 \le s_1$, $s_2 \le n$ and $s_1 \ne s_2$). These pairs indicate that it has been proved that statement $s_1$ implies statement $s_2$.

I need to find the minimum number of additional implications that need to be proved in order to prove that all statements are equivalent.

I have the answer of 2 cases:

1. $n=4$
   $m=0$
   answer: $4$

2. $n=3$
   $m=2$
   pairs:
   $1,2$
   $1,3$
   answer: $2$

I don't understand why the answer is 4 and 2 respectively.

So my question is if somebody could point me in a direction on what I need to learn to solve this? I've never read discrete math but that it has a implications part, is this it?

if so how should I interpret the data to make some neat implications equations e.g. $s_1 \to s_2$ and then make a implications table to calculate it?

Answer 1

In the first case, a graph with four vertices $\{a, b, c, d\}$ but no edges, you need to add at least four edges to make the cycle of statements $$ a \implies b \implies c \implies d \implies a$$ and by a little experimenting, you can see that joining these vertices up into a loop like this is the most efficient way to solve it.

In the second case, you start with three vertices $\{a, b, c\}$ and the two edges $a \implies b$ and $a \implies c$. Firstly, you need to be able to start with $b$ or $c$ and get back to $a$, so you could add the two edges $\{b \implies a, c \implies a\}$, which would then give every implication. Otherwise, you could do something like add the edges $\{b \implies c, c \implies a\}$ which would also do the trick. Either way, adding two edges is the most efficient way to have every implication.

In general, you will be looking for a way to add the least number of edges to make the graph strongly connected. There are nice algorithms to reduce a graph to its strongly connected components, which leave you with the same problem to solve on a directed acyclic graph. So perhaps think of how to solve this problem first for a directed acyclic graph, then for a general graph.

Answer 2

I don't know how to solve the problem, but here some ideas how to reduce it to a bipartite graph. I will demonstrate this with some pictures. We start with a directed graph. The black circle is the end of an edge, usually drawn as an arrowhead. So in the following we have an edge from vertex $a$ to vertex $b$.

First we replace a circle by a new vertex. We draw this new vertex as a square and name it by an uppercase letter.

This step is repeated until there are no more circles.

We are only interested in the sources (no incoming edges) and the sinks (no outgoing edges).

If one has $u$ sources and $w$ sinks one has to add at least $\max\{u,w\}$ directed and at most about $u+w$ edges.

Here we have a solution after adding 4 edges (the minimal possible number):

But I don't know how to find the minimal number of edges to add systematically.