Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
95
0
0.0
(
0
)
Added by
Silvia Butti
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a pair of graphs $textbf{A}$ and $textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $textbf{A}$ to $textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where $textbf{A}$ and $textbf{B}$ are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.
rate research
Read More
Let $G$ be any $n$-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by $1/sqrt{Delta}$ (for example, a random graph $G$ of average degree~$Theta(Delta)$ typically has this property). We show that the $expBig(c frac{log n}{log Delta}Big)$-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a~$G$ is at most $50.1%$ (in fact, at most $tfrac12 + 2^{-Omega(c)}$). For example, in random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n cdot text{polylog}(n)$ edges, $n^{O(1/log log n)} = n^{o(1)}$ rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for maxcut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali--Adams can strongly refute random Boolean $k$-CSP instances with $n^{lceil k/2 rceil + delta}$ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.
The $k$-dimensional Weisfeiler-Leman procedure ($k$-WL), which colors $k$-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are $k$-WL-equivalent if the $k$-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the $k$-WL-equivalence relation becomes finer as $k$ increases. We investigate to what extent standard graph parameters are preserved by $k$-WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of $k$-WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.
We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical setting for the Lovasz local lemma, where each constraint is violated by a small number of forbidden local configurations, our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial whose dependency on $n$ is close to linear, where $n$ is the number of variables. Our main approach is a new technique called state compression, which generalizes the mark/unmark paradigm of Moitra (Moitra, JACM, 2019), and can give fast local-lemma-based sampling algorithms. As concrete applications of our technique, we give the current best almost-uniform samplers for hypergraph colorings and for CNF solutions.
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler and Leman over 50 years ago. 1-WL is the classical color refinement routine. Indistinguishability by $k$-WL is an equivalence relation on graphs that is of fundamental importance for isomorphism testing, descriptive complexity theory, and graph similarity testing which is also of some relevance in artificial intelligence. Focusing on dimensions $k=1,2$, we investigate subgraph patterns whose counts are $k$-WL invariant, and whose occurrence is $k$-WL invariant. We achieve a complete description of all such patterns for dimension $k=1$ and considerably extend the previous results known for $k=2$.
Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of $k$-uniform hypergraphs with a density $alpha$ of constraints, and the $q$-coloring of random graphs with average degree $c$. We show that in the large $k,q$ limit the clustering transition occurs for $alpha = frac{2^{k-1}}{k} (ln k + ln ln k + gamma_{rm d} + o(1))$, $c= q (ln q + ln ln q + gamma_{rm d}+ o(1))$, where $gamma_{rm d}$ is the same constant for both models. We characterize $gamma_{rm d}$ via a functional equation, solve the latter numerically to estimate $gamma_{rm d} approx 0.871$, and obtain an analytic lowerbound $gamma_{rm d} ge 1 + ln (2 (sqrt{2}-1)) approx 0.812$. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at $gamma_{rm r}=1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
