Brewster, Richard C.; Feder, Tomas; Hell, Pavol; Huang, Jing; Macgillivray, Gary Near-unanimity functions and varieties of reflexive graphs. (English) Zbl 1200.05217 SIAM J. Discrete Math. 22, No. 3, 938-960 (2008). Summary: Let \(H\) be a graph and \(k \geq 3\). A near-unanimity function of arity \(k\) is a mapping \(g\) from the \(k\)-tuples over \(V(H)\) to \(V(H)\) such that \(g(x_1, x_2, \cdots, x_k)\) is adjacent to \(g(x^{\prime }_1, x^{\prime }_2, \cdots, x^{\prime }_k)\) whenever \(x_i x^{\prime }_i \in E(H)\) for each \(i = 1,2,\dots ,k\), and \(g(x_1,x_2,\cdots ,x_k) = a\) whenever at least \(k-1\) of the \(x_i\)’s equal \(a\). T. Feder and M.Y. Vardi [“The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory,” SIAM J. Comput. 28, No.1, 57–104 (1998; Zbl 0914.68075)] proved that, if a graph \(H\) admits a near-unanimity function, then the homomorphism extension (or retraction) problem for \(H\) is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs \(H\): they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of \(H\), and we show that these bounds are tight. In particular, it will follow that the arity is bounded by \(n -\sqrt{n}+1\), where \(n = |V(H)|\). We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if \(P\neq NP\), the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming \(P\neq NP\). Cited in 15 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68W25 Approximation algorithms Keywords:graph homomorphism; near unanimity function; homomorphism extension; retraction; dichotomy Citations:Zbl 0914.68075 PDFBibTeX XMLCite \textit{R. C. Brewster} et al., SIAM J. Discrete Math. 22, No. 3, 938--960 (2008; Zbl 1200.05217) Full Text: DOI