there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg [1] & many others.
suppose a class both $X$ and not-$X$ of graphs are proven GI complete. what are the implications of that?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ What do you mean with the class $not-X$ ? Something like: the class of graph that have a certain property $P$ and the class of graphs that don't have that property? In this case I think that for many classes there are no implications at all; for example: $\mathcal{C} = \{ G \mid G \mbox{ has an even number of nodes } \}$ and "$not-{\mathcal{C}}$" are both GI-complete. $\endgroup$– VorDec 20, 2013 at 16:34
-
$\begingroup$ @vor for example regular graphs are GI complete. what is the implication if nonregular graphs are also GI complete? etc... is there always "no implication at all"? $\endgroup$– vznDec 20, 2013 at 16:47
-
1$\begingroup$ a trivial note: if you pick $ \mathcal{C} = \{ (V, \emptyset) \}$ (the class of graphs with no edges), then if both $\mathcal{C}$ and not-$\mathcal{C}$ are GI-complete then $GI \in P$ $\endgroup$– VorDec 20, 2013 at 16:54
-
$\begingroup$ @vor idea, so does it seem to be related to question of whether recognition of the class is in P or NP etc? feel there might be some simple answer but cant quite figure it out immediately $\endgroup$– vznDec 20, 2013 at 17:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Apparently, with graphs of class $X$ and not-$X$ you mean graphs that fulfill a property $X$ and those that don't. It is common that say a graph problem has a different complexity when the input graph is restricted to a certain class of graphs. In this sense, graph isomorphism is no different. As for your question, it is easy to come up with plenty of (even large) classes of graphs. For example, consider graphs that have an even number of vertices, and those that don't. Both are GI-complete, so at least in general, there are no implications.
If this is not satisfying, you need to address what you mean by "non-trivial graphs", but I don't think this would turn out to be too fruitful.
-
$\begingroup$ just take a look at all the classes proved GI complete in the wikipedia link cited. these are all "nontrivial". apparently for none is it known if the class not-$X$ is also GI complete. this seems interesting. it appears there is no nontrivial class known for which both $X$ and not-$X$ are GI complete. $\endgroup$– vznDec 25, 2013 at 18:08
-
1$\begingroup$ @vzn Well, consider connected and disconnected graphs (we can trivially make any graph disconnected by adding an isolated vertex). Or consider the class of graphs that have diameter greater than 2 and radius greater than 1... $\endgroup$– JuhoDec 25, 2013 at 18:50