In a cyclic undirected graph, what is the best (time) algorithm to
identify all connected subgraphs that correspond to a certain
condition? Why? Please give some references. Is this problem solvable
in linear time?

---

Clarification of Question by dave29-ga on 14 Nov 2005 23:47 PST

Sorry i made a mistake. I ment directed. So i will clearify the problem:

I have a directed graph with n nodes which may contain cycles. Anymore
i have a starting node from which i can reach all other nodes. The
graph decomposes into a finite (but very large) count of subgraphs.

A given penalty function f calculates a value over the unordered set
of nodes in the subgraph and returns 1 if it is a valid subgraph.
Adding a "good" node to a uncomplete subgraph increases the value,
whereas a "bad" node leaves the value of the penalty function the
same. So the problem is to find valid combinations of nodes.

On the first sight this seems to me like a variant of the backpack
problem. But maybe this is solvable faster than in exponential time.

By "cyclic undirected graph" I'd assume a finite loop, say of length
n, is meant.  We'll call it C_n for convenience.

While it is clear that all the proper connected subgraphs of C_n are
easily enumerated, up to graph isomorphism anyway (open paths of
length 0 to n-1), it is unclear what "certain condition" might be
intended.

Assuming that such a "certain condition" is invariant with respect to
graph isomorphism (for otherwise I see no hope of making a useful
conclusion), I'm inclined to think that the general Answer is No.  To
have a linear time algorithm strictly means in time proportional to
the "size" of the problem data.  But here the problem data is just the
single input n, whose "size" is log(n).

If all the paths of various lengths that satisfy the "certain
condition" are pre-computed and stored in some fashion that allows for
retrieval in log(n)-lookup time (which seems reasonable), one still
has the difficulty that without some restrictions on results for the
"certain condition", the collection of connected proper subgraphs of
C_n is itself of cardinality n.  So the result for C_n (n arbitrary)
might be an arbitrary subset of these, i.e. 2^n different outcomes,
the indication of which would required n bits to express.

So based solely on considerations of input data size and output data
size, you can see that the relationship is exponential: log(n) bits
input, n bits output.

Naturally there are many conditions of practical interest for which
number of bits needed to express the outcome is smaller.  But I gather
from the vagueness with which "certain condition" is used in stating
the problem that this quite general analysis is intended.

If one permits all the output bits to be looked-up and written "in
parallel", then of course this breaks down the argument.  But in that
case the problem would seem to have little motivation, even as
didactic exercise.


regards, mathtalk-ga

The Clarification makes clear that my earlier Comment has no bearing
on the actual Question posed, but a number of open issues are raised.

There is a description of a "penalty function" f that operates on
subsets of the graph's nodes "and returns 1 if it is a valid
subgraph."  I'm confused, as the next statement seems to say that
adding a "good" node can increase the value (but to what?).  Are you
trying to find a maximum value for f?  The phrase "penalty function"
suggests trying to minimize the value of f.  But the dichotomy of
"valid" versus "invalid" subgraph suggests a function that only
produces values 1 and 0(??).

Where the original Question asks about "all connected subgraphs", this
no longer appears in the restatement.  What is meant by connected for
the directed graphs targeted in the Clarification needs clarification,
if in fact this is still part of the problem.  Also, I'm not sure what
is meant by "a[n] uncomplete subgraph" as mentioned in the
Clarification.

In the absence of some conditions on connectedness(?),
completeness(?), or something else about the edges of the graph, it
seems to be a problem whose domain is (as "penalty function" f
determines) finding valid subsets of the nodes.  You are asking if
there is an efficient algorithm to find all "valid combinations of
nodes".  It would seem that there would potentially be exponentially
many valid combinations that need to be "found", considering that for
n nodes there are 2^n subsets.  It sounds a bit like the function f is
monotonic with respect to subset inclusion on these subsets, and you
want to know if this helps to make the problem more tractable.


regards, mathtalk-ga