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.

Added Addressing some comments:

1. Gerhard wrote "When the adjacency matrix is so given, then your algorithm may work".

This is consistent with experimental results.

sage's implementation of lexicographic product gives me the adjacency matrix this way for free -- tested all graph of orders 5,6. I strongly suspect sage 5.2 can't generate hard instances for (*).

2. Gerhard: permute k of the rows and columns to get the adjacency matrix of a graph isomorphic to T.

I tried this before asking. Basically Gerhard suggests that all bijections from the cartesian product to the matrix will give correct lex. product. I can't prove this and will be interested in a proof. Experimental data (assuming have done it right) suggests that not all bijections give decomposable lex. product. Tested this for several small graphs -- enumerated all (possibly isomorphic) graphs and couldn't find a lex. product that corresponds to the adjacency matrix of the isomorphic graph (of course I may be missing something). My question is about a valid construction or instance of Gerhard's second suggestion. Don't claim the bijection above is unique (found only one more).

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.

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.

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.

Added Addressing some comments:

1. Gerhard wrote "When the adjacency matrix is so given, then your algorithm may work".

This is consistent with experimental results.

sage's implementation of lexicographic product gives me the adjacency matrix this way for free -- tested all graph of orders 5,6. I strongly suspect sage 5.2 can't generate hard instances for (*).

2. Gerhard: permute k of the rows and columns to get the adjacency matrix of a graph isomorphic to T.

I tried this before asking. Basically Gerhard suggests that all bijections from the cartesian product to the matrix will give correct lex. product. I can't prove this and will be interested in a proof. Experimental data (assuming have done it right) suggests that not all bijections give decomposable lex. product. Tested this for several small graphs -- enumerated all (possibly isomorphic) graphs and couldn't find a lex. product that corresponds to the adjacency matrix of the isomorphic graph (of course I may be missing something). My question is about a valid construction or instance of Gerhard's second suggestion. Don't claim the bijection above is unique (found only one more).