Like transitive reduction, but removing vertices rather than edges? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-11-21T14:41:17Z https://cs.stackexchange.com/feeds/question/113389 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/113389 2 Like transitive reduction, but removing vertices rather than edges? Ignat Insarov https://cs.stackexchange.com/users/84119 2019-09-03T18:49:53Z 2019-09-05T15:25:12Z <p>Suppose I have a directed graph <span class="math-container">$G = (V, E)$</span> <em>(or, which is the same, a relation on the set <span class="math-container">$V$</span> as defined by the adjacency matrix)</em> that may contain three vertices <span class="math-container">$x, y, z$</span>, such that <span class="math-container">$xy, xz, yz \in E$</span> — that is to say, the relation restricted to <span class="math-container">$x, y, z$</span> is transitive, there is a triangle. Let us call this situation a <em>"local transitivity"</em>. My goal is to obtain all the subgraphs of <span class="math-container">$G$</span> induced by cutting middle vertices from local transitivities until none remain, which I dub <em>"resolution"</em>.</p> <p>There may be multiple solutions. For instance, consider a graph given by this relation:</p> <pre><code> a b c d a □ ■ ■ □ b □ □ ■ ■ c □ □ □ ■ d □ □ □ □ </code></pre> <p><em>(It looks like a square with one diagonal.)</em></p> <p>There are two ways it can be resolved:</p> <pre><code> a b d a c d a □ ■ □ a □ ■ □ b □ □ ■ c □ □ ■ d □ □ □ d □ □ □ </code></pre> <p>One way I can compute the resolutions of a graph is by giving a <em>"non-deterministic"</em> function <span class="math-container">$f :G \rightarrow \{G\}$</span> that removes any single local transitivity. Repeatedly applying <span class="math-container">$f$</span> to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.</p> <p>One way to define <span class="math-container">$f$</span> is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about <span class="math-container">$|V|^3$</span> such triples.</p> <p>Is there a better way? Is there prior art that I may study?</p> <p>&nbsp;</p> <p><strong>P.S.</strong> Answering to questions from the comments:</p> <ol> <li><blockquote> <p>Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices?</p> </blockquote> <p>In the case I have in mind, it is specifically triangles that I need to remove. But I can see how a generalization may be offered where, given two paths <span class="math-container">$p_1, p_2: a \dots b$</span> such that <span class="math-container">$|p_1| \leq n$</span> and <span class="math-container">$|p_2| \leq m$</span> <em>(counting edges)</em>, we can remove the longer. My specific problem is then the special case with <span class="math-container">$n = 1, m = 2$</span>.</p></li> <li><blockquote> <p>In your example, I think there are more than two ways it can be resolved. For example, you could remove vertex a (from the abc triangle) ...</p> </blockquote> <p>I was thinking that it is only allowed to remove a midpoint from a triangle, so that <em>"initial"</em> and <em>"terminal"</em> vertices cannot be removed, and therefore the length of the shortest path is preserved.</p></li> <li><blockquote> <p>What's your question? Is your question "can I enumerate all triangles faster than <span class="math-container">$O(|V|^3)$</span> time?" Is your question "how efficiently can I find all possible triangle-free subgraphs?"</p> </blockquote> <p>This and that too. Primarily, I need the triangle-free induced subgraphs. Enumerating triangles is only a means to this end, but it may be a useful technique for other algorithms, elsewhere, so would be good to know.</p></li> </ol> https://cs.stackexchange.com/questions/113389/-/113454#113454 1 Answer by D.W. for Like transitive reduction, but removing vertices rather than edges? D.W. https://cs.stackexchange.com/users/755 2019-09-05T15:25:12Z 2019-09-05T15:25:12Z <p>There's a <span class="math-container">$O(n^\omega)$</span>-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex. Here <span class="math-container">$O(n^\omega)$</span> is the running time for matrix multiplication. See, e.g., <a href="https://cs.stackexchange.com/q/74360/755">Number of triangles in an undirected graph</a>, <a href="https://cs.stackexchange.com/q/81028/755">Is it a valid graph canonical form?</a>, <a href="https://cstheory.stackexchange.com/q/9972/5038">https://cstheory.stackexchange.com/q/9972/5038</a>. This may or may not be faster in practice.</p> <p>To enumerate a list of all such triangles can take <span class="math-container">$\Theta(n^3)$</span> time in the worst case, for instance, in the case where you have a complete graph on <span class="math-container">$n$</span> vertices, as then you have <span class="math-container">$\Theta(n^3)$</span> triangles in the graph, so just outputting them takes <span class="math-container">$\Theta(n^3)$</span> time.</p>