3
$\begingroup$

Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.

I'm trying to partition the graph to the minimal number of connected sets.

Sets $A_0, A_1, ..., A_k$ are connected if you can reach from some vertex in $A_0$ to some vertex in $A_k$.

Assume the following $k$-partite graph (directed acyclic heading right):

enter image description here

In the above example, the minimal number of connected sets is $3$: $(0,1,2)$, $(3, 4, 5)$, $(6)$.

This problem can be solved using a reduction to the Set-Cover problem, however I think it's easier than that.

My idea is to greedily find the longest path from set $0$ to set $k$, then from set $k+1$ to set $j$, until reaching the last set.

Can anyone see in what cases it won't work? Any ideas on how to approach such proof of correctness?

Thanks

$\endgroup$
4
  • $\begingroup$ Can you state the question more precisely? What exactly do you mean by "minimal number of connected sets"? Do you want a partition of the sets? Do you just want a cover of the sets? What's the context where you encountered this task or the motivation? $\endgroup$
    – D.W.
    Jun 21 at 21:55
  • $\begingroup$ I'm looking for the minimal partition of the graph, I've edited the question so it might be more clear now. The context isn't related to a known problem afaik, just something I'm investigating. $\endgroup$
    – Philip L
    Jun 21 at 21:58
  • $\begingroup$ Please edit the question to make that clear. I don't see anything in the question that states a requirement that the connected sets must be disjoint, or what the elements of the sets are. We want questions to stand on their own. People shouldn't have to read the comments to understand what is being asked. An example is not a substitute for a clear, general problem statement. $\endgroup$
    – D.W.
    Jun 21 at 22:00
2
$\begingroup$

Your greedy approach works. Let's first find an abstraction of your problem that makes it easier to come up with a proof:

We have a family $F$ of sets of consecutive integers in $\{1,\ldots,k\}$ (we will call them intervals) that is closed under taking subintervals, i.e. for any $a\leq b\leq c\leq d$, if $\{a,\ldots,d\} \in F$, then $\{b,\ldots,c\} \in F$ also. Your problem is to find a minimum number of intervals in $F$ that covers $\{1,\ldots,k\}$. Converting from your graphic description to the set of intervals is not hard.

Another useful fact about $F$ is, as OP pointed out, that for every $i\in \{1,\ldots,k\}$, $\{i\}$ is in F.

My suggestion for a proof goes like this: Take any optimal solution $S^*$. Show that you can switch out each interval in $S^*$ with one in your greedy solution to obtain a set of equally few intervals. To this end, the fact that $F$ is closed under taking subintervals comes in handy.

Specifically, let $S$ be your greedy solution. We want to show for any $i$, the first (leftmost) $i$ intervals in $S$ cover at least as much as the first $i$ intervals in $S^*$. We can show this by induction.

For the base case, it is vacuously true that the first zero intervals in $S$ cover at least as much of $\{1,\ldots,k\}$ as the first zero intervals of $S^*$, which is nothing.

For the induction step, suppose that the hypothesis holds for the $i-1$ first intervals of $S$ and $S^*$, and we show that it is the case also for the i'th interval. Say that the first $i-1$ intervals in $S$ cover $\{1,\ldots,r\}$ and the first $i-1$ intervals in $S^*$ cover $\{1,\ldots,r^*\}$. By our hypothesis, $r \geq r^*$. $s^*_i$ then ends at some $t^*$. If $t^* > r$, then, since $F$ is closed under taking subintervals, there is an interval going from $r+1$ to $t^*$. And $s_i$ is clearly not smaller than this interval. If $t^* \leq r$, then we know that $\{r+1\}$ is an interval in $F$, and again, $s_i$ is clearly not smaller than this interval. Therefore, if $s_i$ ends at $t$, then $t \geq t^*$. This concludes the proof.

I hope this rather thorough writeup can be of any help into how one can design a proof that a greedy algorithm is optimal. It often comes down to showing how, at each step, we have an optimal subsolution. If you took any optimal solution and switched out the first few items for the items you found, you would end up with just as good a solution. In our case, we can, for any $i$, take the interval set $(s_1,\ldots,s_{i_1},s^*_i,\ldots,s^*_k)$. This is a solution (in fact, some elements may get covered twice or more, but this is not a problem).

$\endgroup$
1
  • $\begingroup$ So in my case, each $S_{ij} \in F$ ($S_{ij} = \{i,..,j\}$) represents a valid path between $A_i$ and $A_j$, and $\forall{i} \in \{1,...,k\}: S_{ii} \in F$. That's the part of converting the graphic description. I'm not sure what you mean by switching out intervals. can you please elaborate? $\endgroup$
    – Philip L
    Jun 29 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.