5
$\begingroup$

I would like to find the largest set of vertices in a directed graph. This set should not contain a cycle with exactly three vertices. Cycles with less vertices aren't possible with the given graphs; larger cycles can be in the set.

Do you know an algorithm for that?

$\endgroup$
  • $\begingroup$ @moose: So you're asking for an maximum induced subgraph without directed triangle, right? $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 28 '11 at 8:00
  • $\begingroup$ If so, this is likely to be NP-hard, while I haven't found such a reference. Maybe it can be derived from some known NP-hard results of detecting induced subgraphs, since most of them are pretty hard. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 28 '11 at 8:16
  • $\begingroup$ It should be easy to reduce the 3-hitting set problem, hence NP-hard. $\endgroup$ – Yoshio Okamoto Mar 28 '11 at 9:21
  • $\begingroup$ @Hsien-Chih Chang 張顯之: Exactly. Could you please suggest some knowen NP-hard results of detecting induced subgraphs? If you post it as an answer, I'll accept it if nobody else gives me a better answer until Wednesday. $\endgroup$ – Martin Thoma Mar 28 '11 at 9:54
  • 1
    $\begingroup$ I'd suggest changing the title to "Finding the largest subgraph without a directed triangle" or something like that. $\endgroup$ – arnab Mar 28 '11 at 20:41
14
$\begingroup$

The problem of finding a maximum set with no induced directed triangles is NP-complete via a reduction from maximum independent set.

Let G=(V,E) be an undirected graph and k be an integer, for which we wish to know whether there is an independent set of at least k vertices. Let |V|=n. From G construct a directed graph G'=(V',A'), where V' consists of the disjoint union of V and n additional vertices. For each undirected edge in G create two directed edges between the same vertices in G'. In addition, connect each of the n additional vertices in G' by edges in both directions to the vertices in V, but do not add edges between any two of the n additional vertices.

Then, a triangle-free set of vertices in G' consists either of a subset of V only (with at most n vertices) or it contains some vertices in the set of additional vertices together with an independent set of vertices in G. Therefore, there exists a triangle-free set of size n+k in G' iff there exists an independent set of size k in G.

However, this reduction produces many 2-cycles, so it leaves open the possibility that the problem might be easier in the case that the input graph has no 2-cycles, which you say is the case for your inputs. Unfortunately this special case is still hard: a more complicated reduction based on the same idea shows that the problem remains NP-complete even for 2-cycle-free graphs. In the more complicated reduction, add mn additional vertices rather than simply n. Replace each undirected edge in G by a directed edge, oriented arbitrarily. For each directed edge uv connecting two vertices of V, make n additional vertices in V', each of them connected to u and v to form a directed triangle. Then the resulting graph has mn+k vertices in a triangle-free set iff the original graph has k vertices in an independent set.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks David for your detailed answer. It will take some time for me to understand your post completely. May I contact you if I have some more questions to this topic? $\endgroup$ – Martin Thoma Mar 30 '11 at 21:31

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.