1
$\begingroup$

I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.

Best, Vany

Improve this question
$\endgroup$
4
  • $\begingroup$ Okay, so I found out that the problem in general seems to be NP-hard ("Unfortunately, enumerating all the cutsets is a well-known NP-hard problem [15] and our experiments demonstrate this exponential growth rate of the computation time.", Lin et al., 2003 ieeexplore.ieee.org/document/1214299 ), and it makes sense that in general the complexity is exponential because for a complete graph, all 2^n-2 possibilities have to be listed. However, I am still interested if there is a way to find out how many possibilities there are for a given graph and to enumerate them in O(cuts). $\endgroup$
    – user46778
    Sep 7, 2017 at 16:20
  • $\begingroup$ I am not sure I understand the definition of a minimal cut set. Is it a partition of the vertices of $G$ into $S$ and $T$ so that the induced graphs $G[S]$ and $G[T]$ are connected? Equivalently, a set of edges whose removal disconnects the graph into exactly two connected components? $\endgroup$
    – Sasho Nikolov
    Sep 9, 2017 at 0:29
  • $\begingroup$ Dear Sasho, exactly. A cut set is defined as a subset of edges which when removed disconnect the graph. A cut set is minimal if none of it subsets is a cut set, which is equivalent to the formulation that a minimal cut set disconnects the graph into exactly two connected components. $\endgroup$
    – user46778
    Sep 10, 2017 at 14:17
  • 1
    $\begingroup$ I would take that paper you reference with a grain of salt. For one thing, it's a bit nonsensical to say that a problem in which you are asked to list an exponential number of objects is NP-hard. For another, reference [15] shows that counting the number of minimum cardinality cutsets is #P-hard. They don't say anything about counting minimal cutsets, as in your definition. $\endgroup$
    – Sasho Nikolov
    Sep 10, 2017 at 15:38

1 Answer 1

Reset to default
-1
$\begingroup$

dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version. Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.

Improve this answer
$\endgroup$

Your Answer

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