MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You seem to be assuming that $T$ is given with the vertices numbered in a particular order. I don't know why this is useful or interesting. – Brendan McKay Sep 13 '12 at 12:29
...and $T$ is numbered this way. – joro Sep 13 '12 at 13:10
When the adjacency matrix is so given, then your algorithm may work (I'm still looking, so I say may instead of does). Suppose I take the adjacency matrix of a large graph and a small number k>1, and permute k of the rows and columns to get the adjacency matrix of a graph isomorphic to T. What does (*) do? Gerhard "Preparing A System Design Response" Paseman, 2012.09.13 – Gerhard Paseman Sep 13 '12 at 15:17
...Some stupid comments deleted. – joro Sep 14 '12 at 11:29
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.