Talk:Destroying rigidity

Minimum cut of hypergraphic matroids -- Tamás Király 14:54, 28 December 2009 (UTC)

A special case of (hypergraphic) count matroids is the class of k-circuit matroids of hypergraphs, see Hypergraphic matroid. In Egres Quick Proof No. 2009-05 I described how the minimum cut can be found in polynomial time in this case.

NP-completeness of gammoids -- Lapchi 06:28, 5 April 2010 (UTC)

Is it possible to sketch why finding a minimum cocircuit in a gammoid is NP-complete? I could not find a copy of McCormick's thesis online.

Re: NP-completeness of gammoids -- Tamás Király 11:17, 9 April 2010 (UTC)

The proof, attributed to Stockmeyer in the thesis, shows that finding the minimum circuit of a transversal matroid is NP-complete. The problem reduced to it is deciding if there is a clique of size k in a graph. We assume that [math]k \geq 4[/math]. Given a simple graph G=(V,E), we construct a bipartite graph H=(A,B;F) with [math]|A|=|E|[/math] and [math]|B|=|V|+\binom{k}{2}-k-1[/math]. The first [math]|V|[/math] nodes of B correspond to nodes of G, and are connected to the nodes corresponding to incident edges. The other nodes of B are connected to all nodes in A. Let M be the transversal matroid on ground set A defined by H. It is not hard to see that M cannot have a circuit of size less than [math]\binom{k}{2}[/math] because G is simple, and M has a circuit of size [math]\binom{k}{2}[/math] if and only if G has a clique of size k.