Found a possible reduction from recognizing [lexicographic product of graphs](https://en.wikipedia.org/wiki/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](http://drememi.ludost.net/lexp.pdf) -- 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.



Counterexamples for this algorithm for recognizing lexicographic product of graphs?
Gerhard's suggestion:



> 
> permute k of the rows and columns to get the adjacency matrix of a graph isomorphic to T. What does (\*) do? 
> 
> 
> 


Made the algorithm fail and this qualifies as a valid counterexample to me.


