research-article

On the complexity of H-coloring for special oriented trees

Author:

Jakub BulnAuthors Info & Claims

European Journal of Combinatorics, Volume 69, Issue C

Pages 54 - 75

https://doi.org/10.1016/j.ejc.2017.10.001

Published: 01 March 2018 Publication History

Abstract

For a fixed digraph H, the H-coloring problem is the problem of deciding whether a given input digraph G admits a homomorphism to H. The CSP dichotomy conjecture of Feder and Vardi is equivalent to proving that, for any H, the H-coloring problem is in P or NP-complete. We confirm this dichotomy for a certain class of oriented trees, which we call special trees (generalizing earlier results on special triads and polyads). Moreover, we prove that every tractable special oriented tree has bounded width, i.e., the corresponding H-coloring problem is solvable by local consistency checking. Our proof relies on recent algebraic tools, namely characterization of congruence meet-semidistributivity via pointing operations and absorption theory.

References

[1]

E. Allender, M. Bauland, N. Immerman, H. Schnoor, H. Vollmer, The complexity of satisfiability problems: Refining schaefers theorem, in: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29September 2, 2005 Proceedings, 2005, pp. 7182.

Digital Library

[2]

L. Barto, The dichotomy for conservative constraint satisfaction problems revisited, in: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, IEEE Computer Society, 2011, pp. 21-24.

Digital Library

[3]

L. Barto, J. Bul.n, CSP dichotomy for special polyads, Internat. J. Algebra Comput., 23 (2013) 1151-1174.

[4]

L. Barto, M. Kozik, Constraint satisfaction problems of bounded width, in: 50th Annual IEEE Symposium on Foundations of Computer Science, 2009 FOCS 09, 2009, pp. 595603.

Digital Library

[5]

L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Logical Methods Comput. Sci., 8 (2012) 27.

[6]

L. Barto, M. Kozik, Robust Satisfiability of Constraint Satisfaction Problems, in: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC 12, ACM, New York, NY, USA, 2012, pp. 931-940.

Digital Library

[7]

L. Barto, M. Kozik, Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61 (2014) 19.

Digital Library

[8]

L. Barto, M. Kozik, Absorption in universal algebra and CSP, in: The Constraint Satisfaction Problem: Complexity and Approximability, 2017, pp. 45-77.

[9]

L. Barto, M. Kozik, M. Marti, T. Niven, CSP dichotomy for special triads, Proc. Amer. Math. Soc., 137 (2009) 2921-2934.

[10]

L. Barto, M. Kozik, T. Niven, The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput., 38 (2008) 1782-1802.

Digital Library

[11]

L. Barto, M. Kozik, .D. Stanovsk, Maltsev conditions, lack of absorption, and solvability, Algebra Univ., 74 (2015) 185-206.

[12]

C. Bergman, Chapman and Hall/CRC, Boca Raton, 2011.

[13]

J. Berman, P. Idziak, .P. Markovi, R. McKenzie, M. Valeriote, R. Willard, Varieties with few subalgebras of powers, Trans. Amer. Math. Soc., 362 (2010) 1445-1473.

[14]

V.G. Bodnaruk, L.A. Kalunin, V.N. Kotov, B.A. Romov, Galois theory for post algebras. i, II. Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoi SSR, Kibernetika, 3 (1969) 1-9.

[15]

A. Bulatov, Tractable conservative constraint satisfaction problems, in: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 03, IEEE Computer Society, Washington, DC, USA, 2003, pp. 321.

Digital Library

[16]

A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, J. ACM, 53 (2006) 66-120.

Digital Library

[17]

A. Bulatov, P. Jeavons, A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005) 720-742.

Digital Library

[18]

A. Bulatov, M. Valeriote, Recent results on the algebraic approach to the CSP, in: Complexity of Constraints, 2008, pp. 68-92.

Digital Library

[19]

J. Buln, .D. Deli, M. Jackson, T. Niven, On the reduction of the CSP dichotomy conjecture to digraphs, in: Lecture Notes in Computer Science, vol. 8124, Springer Berlin Heidelberg, 2013, pp. 184-199.

Digital Library

[20]

J. Buln, .D. Deli, M. Jackson, T. Niven, A finer reduction of constraint problems to digraphs, Log. Methods Comput. Sci., 11 (2015).

[21]

T. Feder, Classification of homomorphisms to oriented cycles and of k-partite satisfiability, SIAM J. Discret. Math., 14 (2001) 471-480.

Digital Library

[22]

T. Feder, M.Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28 (1999) 57-104.

Digital Library

[23]

D. Geiger, Closed systems of functions and predicates, Pacific J. Math., 27 (1968) 95-100.

[24]

W. Gutjahr, E. Welzl, G. Woeginger, Polynomial graph-colorings, Discrete Appl. Math., 35 (1992) 29-45.

Digital Library

[25]

R. Hggkvist, P. Hell, D.J. Miller, V. Neuman.Lara, On multiplicative graphs and the product conjecture, Combinatorica, 8 (1988) 63-74.

[26]

P. Hell, J. Neetil, Graphs and Homomorphisms, in: Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, New York, 2004.

[27]

P. Hell, J. Neetil, X. Zhu, Complexity of tree homomorphisms, Discrete Appl. Math., 70 (1996) 23-36.

Digital Library

[28]

P. Hell, J. Neetil, X. Zhu, Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc., 348 (1996) 1281-1297.

[29]

P. Hell, J. Neetil, On the complexity of h-coloring, J. Comb. Theory Ser. B, 48 (1990) 92-110.

Digital Library

[30]

P. Idziak, R. Mckenzie, R. Willard, Tractability and learnability arising from algebras with few subpowers, in: LICS07, IEEE Computer Society, 2007, pp. 213-224.

Digital Library

[31]

P. Jeavons, D. Cohen, M. Gyssens, Closure properties of constraints, J. ACM, 44 (1997) 527-548.

Digital Library

[32]

G. Kun, Constraints, MMSNP and expander relational structures, Combinatorica, 33 (2013) 335-347.

Digital Library

[33]

B. Larose, Algebra and the complexity of digraph CSPs: a survey, in: The Constraint Satisfaction Problem: Complexity and Approximability, 2017, pp. 267-285.

[34]

B. Larose, P. Tesson, Universal algebra and hardness results for constraint satisfaction problems, Theoret. Comput. Sci., 410 (2009) 1629-1647.

Digital Library

[35]

B. Larose, L. Zdori, Bounded width problems and algebras, Algebra Univ., 56 (2007) 439-466.

[36]

M. Marti, R. McKenzie, Existence theorems for weakly symmetric operations, Algebra Universalis, 59 (2008) 463-489.

[37]

T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC78, ACM, New York, NY, USA, 1978, pp. 216-226.

Digital Library

Cited By

Bodirsky MBulín JStarke FWernthaler M(2023)The smallest hard treesConstraints10.1007/s10601-023-09341-828:2(105-137)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1007/s10601-023-09341-8
Foucaud FHocquard HLajou DMitsou VPierron T(2022)Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical ComplexityAlgorithmica10.1007/s00453-021-00918-484:5(1183-1212)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s00453-021-00918-4
Beaudou LFoucaud FMadelaine FNourine LRichard G(2019)Complexity of Conjunctive Regular Path Query HomomorphismsComputing with Foresight and Industry10.1007/978-3-030-22996-2_10(108-119)Online publication date: 15-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-22996-2_10

On the complexity of H-coloring for special oriented trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Space complexity of list H-colouring: a dichotomy
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by Bulatov (2003). We ...
The complexity of choosing an H-colouring (nearly) uniformly at random
Parameterized complexity of vertex colouring

For a family F of graphs and a nonnegative integer k, F + ke and F - ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F + kv denotes the family of graphs that can be made into ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image European Journal of Combinatorics

European Journal of Combinatorics Volume 69, Issue C

March 2018

184 pages

ISSN:0195-6698

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Academic Press Ltd.

United Kingdom

Publication History

Published: 01 March 2018

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bodirsky MBulín JStarke FWernthaler M(2023)The smallest hard treesConstraints10.1007/s10601-023-09341-828:2(105-137)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1007/s10601-023-09341-8
Foucaud FHocquard HLajou DMitsou VPierron T(2022)Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical ComplexityAlgorithmica10.1007/s00453-021-00918-484:5(1183-1212)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s00453-021-00918-4
Beaudou LFoucaud FMadelaine FNourine LRichard G(2019)Complexity of Conjunctive Regular Path Query HomomorphismsComputing with Foresight and Industry10.1007/978-3-030-22996-2_10(108-119)Online publication date: 15-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-22996-2_10

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents