Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimitations of Algebraic Approaches to Graph Isomorphism Testing
186
0
0.0
(
0
)
Added by
Martin Grohe
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Grobner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if the graphs are isomorphic, and then to (try to) decide satisfiability of the system using, for example, the Grobner basis algorithm. In some cases this can be done in polynomial time, in particular, if the equations admit a bounded degree refutation in an algebraic proof systems such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on the polynomial calculus degree over all fields of characteristic different from 2 and also linear lower bounds for the degree of Positivstellensatz calculus derivations. We compare this approach to recently studied linear and semidefinite programming approaches to isomorphism testing, which are known to be related to the combinatorial Weisfeiler-Lehman algorithm. We exactly characterise the power of the Weisfeiler-Lehman algorithm in terms of an algebraic proof system that lies between degree-k Nullstellensatz and degree-k polynomial calculus.
rate research
Read More
In recent years, we have seen several approaches to the graph isomorphism problem based on generic mathematical programming or algebraic (Grobner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of nonisomorphic CFI-graphs (introduced by Cai, Furer, and Immerman in 1992 as hard examples for the combinatorial Weisfeiler-Leman algorithm) cannot be distinguished by these mathematical algorithms. A notable exception were the algebraic algorithms over the field GF(2), for which no lower bound was known. Another, in some way even stronger, approach to graph isomorphism testing is based on solving systems of linear Diophantine equations (that is, linear equations over the integers), which is known to be possible in polynomial time. So far, no lower bounds for this approach were known. Lower bounds for the algebraic algorithms can best be proved in the framework of proof complexity, where they can be phrased as lower bounds for algebraic proof systems such as Nullstellensatz or the (more powerful) polynomial calculus. We give new hard examples for these systems: families of pairs of non-isomorphic graphs that are hard to distinguish by polynomial calculus proofs simultaneously over all prime fields, including GF(2), as well as examples that are hard to distinguish by the systems-of-linear-Diophantine-equations approach. In a previous paper, we observed that the CFI-graphs are closely related to what we call group CSPs: constraint satisfaction problems where the constraints are membership tests in some coset of a subgroup of a cartesian power of a base group (Z_2 in the case of the classical CFI-graphs). Our new examples are also based on group CSPs (for Abelian groups), but here we extend the CSPs by a few non-group constraints to obtain even harder instances for graph isomorphism.
We give a family of counter examples showing that the two sequences of polytopes $Phi_{n,n}$ and $Psi_{n,n}$ are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.
Let $F$ be a connected graph with $ell$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $ell$, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs $K_ell$ and $K_{ell-1}$. We show that, for some $F$, the existence of an $F$ subgraph in emph{sufficiently large} connected graphs is definable with quantifier depth $ell-3$. On the other hand, this is never possible with quantifier depth better than $ell/2$. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some $F$ be arbitrarily small comparing to $ell$ but never smaller than the treewidth of $F$. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of $F$. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs $F$ on 4 vertices.
Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic. The recognition problem of $I(F)$, known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining or estimating the value of $W[F]$. Using Olarius characterization of paw-free graphs, we show that $I(K_3+e)$ is definable by a first-order sentence of quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an example of a graph $F$ with $W[F]$ strictly less than the number of vertices in $F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a general lower bound $W[F]>(1/2-o(1))t$, where the function in the little-o notation approaches 0 as $t$ inreases. This bound holds true even for a related parameter $W^*[F]le W[F]$, which is defined as the minimum $k$ such that $I(F)$ is definable in the infinitary logic $L^k_{inftyomega}$. We show that $W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$ being the path graph on 4 vertices. Using the lower bound for $W[F]$, we also obtain a succintness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.
Let $v(F)$ denote the number of vertices in a fixed connected pattern graph $F$. We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ is expressible by a first-order sentence of quantifier depth $frac23,v(F)+1$, assuming that the host graph is sufficiently large and connected. On the other hand, this is impossible for any $F$ with using less than $frac23,v(F)-2$ first-order variables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
