Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is related to the complexity of graph isomorphism, almost surely the algorithm is incomplete.
Strangely to me, the algorithm works in practice against both sage's implementation of the product and recognizes a construction of a graph given in a paper for 1000 real graphs.
The full algorithm (*) is available here -- 3 pages.
Let $\bullet$ denote the lexicographic product. My pain is: given $ T = G \bullet H $, find $G,H$. By construction the vertices of $T$ are the cartesian product $V(G) \times V(H)$, but it practice the algorithm works with the adjacency matrix of $T$ (indexed from 0) and we don't know the map to the cartesian product. So we need maps from the CP to the matrix and the inverse. Let $|V(G)|=n$, $|V(H)|=m$. The vertices of $G,H$ are $[0..n-1],[0..m-1]$. One map from $V(G) \times V(H) \to [0 .. nm-1]$ is $g_m(a,b)=am + b$. The inverse map is $f_{n,m}(a)=(\lfloor(a/m)\rfloor,a \mod m)$. This is a bijection.
These maps coincide with sage's implementation of $\bullet$.
So given the adjacency matrix of $T$ and $n,m$ we use the map $f_{n,m}$ and run (*).
I am pretty sure if $T$ was computed by sage's algorithm $G,H$ would be found in polynomial time via the reduction to 2SAT. ($n,m$ are found by iterating over the divisors).
To find a counterexample to (*) it would suffice to find the adjacency matrix of $T = G \bullet H$ for which the maps $f_{n,m}$ and $g_m$ don't lead to lexicographic decomposition. If the above happens, appears to me sage's lexicographic product would be incomplete too.
So any counterexamples to (*)?
Hard instances will be appreciated too.
