Paper Info
Title
The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order.
Abstract
Let $C$ be a class of graphs and $pi$ be a graph parameter. Let $Phi$ be a formula in the first-order language containing only the adjacency and the equality relations. We say that $Phi$ emph{defines $C$ on connected graphs with sufficiently large $pi$} if there is a constant $k$ such that, for every connected graph $G$ with $pi(G)ge k$, $Phi$ is true on $G$ exactly when $G$ belongs to $C$. For a fixed connected graph $F$, let $S(F)$ denote the class of all graphs containing $F$ as a subgraph. Let $D_pi(F)$ denote the minimum quantifier depth of a formula $Phi$ defining $S(F)$ on connected graphs with sufficiently large $pi$. We have $D_v(F)ge D_{tw}(F)ge D_kappa(F)$, where $v(G)$ denotes the number of vertices in a graph $G$, $tw(G)$ is the treewidth of $G$, and $kappa(G)$ is the connectivity of~$G$. We obtain the following results. - There are graphs $F$ such that $D_v(F)$ is strictly smaller than the number $n$ of vertices in $F$. In particular, $D_v(P_n)=n-1$ for the path graphs on $nge4$ vertices. Moreover, there are some trees $F$ such that $D_v(F)le n-3$. - On the other hand, $D_v(F)=D_{tw}(F)=n$ if $F$ has no vertex of degree 1. In general, $D_v(F)u003en/2$ unless $F=P_2$ or $P_3$. - $D_{tw}(F)ge tw(F)$ for every $F$. Over trees $F$ with $n$ vertices, the values of $D_{tw}(F)$ occupy the almost full spectrum ${1,5,ldots,n}$. The minimum value $D_{tw}(F)=1$ is attained if $F$ is a subtree of a subdivided 3-star $K_{1,3}$. The maximum $D_{tw}(K_{1,n-1})=n$ is attained for the star graphs on $nge5$ vertices. - $D_kappa(F)gefrac mn+2$ whenever the number $m$ of edges in $F$ is larger than the number $n$ of vertices. Over graphs $F$ with $n$ vertices, the values of $D_kappa(F)$ occupy the almost full spectrum ${1,3,ldots,n}$.
Year
Venue
Field
2016
arXiv: Computational Complexity
Discrete mathematics,Combinatorics,Descriptive complexity theory,Subgraph isomorphism problem,Mathematics
DocType
Volume
Citations 
Journal
abs/1607.08067
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Oleg Verbitsky119127.50
Maksim Zhukovskii224.51