Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Effectiveness of Structural Restrictions for Hybrid CSPs

verfasst von : Vladimir Kolmogorov, Michal Rolínek, Rustem Takhanov

Erschienen in: Algorithms and Computation

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism \({\mathbf {R}\rightarrow \varvec{\Gamma }}\) between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side \(\varvec{\Gamma }\) is fixed and the left side \(\mathbf {R}\) is unconstrained.
Far fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that \(\mathbf {R}\) belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template \(\varvec{\Gamma }\) (from a certain class of languages) for which the problem is tractable when \(\mathbf {R}\) is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.
As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)
Nächstes Kapitel Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
Fußnoten
1
We will allow two possibilities: (i) weights are positive integers, and the length of the description of \(\mathcal{I}\) grows linearly with \(w(f,\mathbf {v})\); (ii) weights are positive rationals. All our statements for VCSPs will hold under both models. Note that in the literature weights \(w(f,\mathbf {v})\) are usually omitted, and T is allowed to be a multiset rather than a set; this is equivalent to model (i). Including weights will be convenient for hybrid VCSPs.
 
Literatur
1.
Appel, K., Haken, W.: Every planar map is four colorable. Part i: discharging. Illinois J. Math. 21(3), 429–490 (1977)MathSciNetMATH
2.
Barto, L., Kozik. M.: New conditions for Taylor varieties and CSP. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11–14 July 2010, Edinburgh, UK, pp. 100–109 (2010)
3.
Barto, L., Kozik, M., Niven, T.: 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(5), 1782–1802 (2009)MathSciNetCrossRefMATH
4.
5.
Bulatov, A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic, 12(4) (2011). Article 24
6.
Bulatov, A., Krokhin, A., Jeavons, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005)MathSciNetCrossRefMATH
7.
Bulín, J., Delić, D., Jackson, M., Niven, T.: On the reduction of the CSP dichotomy conjecture to digraphs. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 184–199. Springer, Heidelberg (2013) CrossRef
8.
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158. ACM, New York (1971)
9.
10.
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57–104 (1998)MathSciNetCrossRefMATH
11.
12.
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1:1–1:24 (2007)MathSciNetCrossRefMATH
13.
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York (1988)CrossRefMATH
14.
Hell, P., Nešetřil, J.: On the complexity of h-coloring. J. Comb. Theory, Series B 48(1), 92–110 (1990)CrossRefMATH
15.
Jeavons, P., Krokhin, A., Živný, S.: The complexity of valued constraint satisfaction. Bull. EATCS 113, 21–55 (2014)
16.
17.
Jégou, P.: Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In: AAAI, pp. 731–736 (1993)
18.
Kolmogorov, V., Rolínek, M., Takhanov, R.: Effectiveness of structural restrictions for hybrid CSPs (2015). arXiv1504.​07067
19.
Kuznetsov, A.V.: Algebra of logic and their generalizations. In: Mathematics in USSR for 40 years, vol. 1, pp. 105–115. Fizmatgiz Moscow (1959)
20.
Maróti, M., McKenzie, R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59(3–4), 463–489 (2008)MathSciNetCrossRefMATH
21.
Nešetřil, J., Ossona de Mendez, P.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 651–664. Springer, Heidelberg (2003) CrossRef
22.
Post, E.L.: On The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton (1941)
23.
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226 (1978)
24.
Siggers, M.H.: A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Universalis 64(1–2), 15–20 (2010)MathSciNetCrossRefMATH
25.
Swarts, J.: The complexity of digraph homomorphisms: Local tournaments, injective homomorphisms and polymorphisms. Ph. D. thesis, University of Victoria, Canada (2008)
26.
Takhanov, R.S.: A dichotomy theorem for the general minimum cost homomorphism problem. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 657–668 (2010)
Metadaten
Titel
Effectiveness of Structural Restrictions for Hybrid CSPs
verfasst von
Vladimir Kolmogorov
Michal Rolínek
Rustem Takhanov
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Algorithms and Computation

Print ISBN: 978-3-662-48970-3

Electronic ISBN: 978-3-662-48971-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48971-0_48

Premium Partner

    Bildnachweise