Does anyone know a specific polynomial-time algorithm to detect if a given signed graph contains an odd-K4 as a signed minor? By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite graphs).
 A: Yes, in my PhD thesis, we prove the stronger result that for any fixed signed graph $(G, \Sigma)$, there is a polynomial-time algorithm to test if an input signed graph contains a $(G, \Sigma)$-minor.  Actually, we prove the stronger result that for any abelian group $\Gamma$, testing for a fixed $\Gamma$-labelled minor can be done in polynomial time (signed graphs correspond to the case $\Gamma=\mathbb{Z} / 2 \mathbb{Z}$).  
As a word of warning, the algorithm is rather complicated.  For example, the special case that $\Gamma$ is the trivial group includes minor testing (for graphs), which requires much of the Graph Minors machinery developed by Robertson and Seymour.  
If you only care about odd-$K_4$-minors, there is an easier algorithm of Kawarabayashi, Li and Reed here.
A: As a consequence of 
[Seymour, P.D., The matroids with the max-flow min-cut property, JCT B, 23 (1977), p. 189-222], 
a finite signed graph has an odd $K^4$ as signed minor 
if and only if 
the system $\mathcal{S}$ of linear inequalities defining
its negative-circuit-incidence-vector-polyhedron 
is totally dual integral. 
As a consequence of [Cook, W., Lovász, L., Schrijver, A., A polynomial-time test for total dual integrality in fixed dimension (1984)] there exists an algorithm which decides in time polynomial in the number of edges of the given graph, whether $\mathcal{S}$ is totally dual integral. 
I am not sure whether this conforms with your request for a specific algorithm, specific being an informal notion. Right off the bat I am unsure how much the result of Cook--Lovász--Schrijver has been improved in the intervening thirty years. 
Should you decide to further pursue this direction (i.e., not working with the combinatorics proper but passing to a system of linear inequations, then 
it might help to 
keep in mind that the above-mentioned system of linear inequalities is a 
zero-one-system
have a look at recent work of 
Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovi&cacute;.
