By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite graphs).
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Isn't brute force a polynomial time algorithm? Gerhard "Six Is Smaller Than N?" Paseman, 2017.04.19. $\endgroup$– Gerhard PasemanCommented Apr 19, 2017 at 15:21
-
$\begingroup$ @GerhardPaseman There isn't a polynomial brute force algorithm if you want to test for minors. Brute force only works if you want to test if you have an odd-K_4 as a subgraph. $\endgroup$– Tony HuynhCommented Apr 19, 2017 at 19:27
-
$\begingroup$ Really? I guess I do not understand. I thought iterating over 4-tuples of vertices and doing a polynomial amount of work at each tuple is what is required. Maybe a minor is more like a quotient? Gerhard "Easily Gets These Things Confused" Paseman, 2017.04.19. $\endgroup$– Gerhard PasemanCommented Apr 19, 2017 at 19:42
-
$\begingroup$ @GerhardPaseman en.wikipedia.org/wiki/Graph_minor is fairly informative - edge contractions are the piece you're missing. $\endgroup$– Steven StadnickiCommented Apr 19, 2017 at 19:45
-
$\begingroup$ (And note that testing a given 4-tuple of vertices by just looking for paths between all pairs of the 4-tuple doesn't work, because those paths aren't guaranteed to be disjoint from each other.) $\endgroup$– Steven StadnickiCommented Apr 19, 2017 at 19:49
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Apr 19, 2017 at 19:21
$\begingroup$
$\endgroup$
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ć.
answered Apr 19, 2017 at 15:58