×

Near-unanimity functions and varieties of reflexive graphs. (English) Zbl 1200.05217

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\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W25 Approximation algorithms

Citations:

Zbl 0914.68075
PDFBibTeX XMLCite
Full Text: DOI