1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Sep 13, 2012 at 12:29
  • $\begingroup$ ...and $T$ is numbered this way. $\endgroup$
    – joro
    Sep 13, 2012 at 13:10
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 13, 2012 at 15:17
  • $\begingroup$ ...Some stupid comments deleted. $\endgroup$
    – joro
    Sep 14, 2012 at 11:29

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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