3 Search Results for "Fulla, Peter"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.24
Temporal Valued Constraint Satisfaction Problems

Authors: Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the computational complexity of the valued constraint satisfaction problem (VCSP) for every valued structure over ℚ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in (ℚ; <), and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures that contain a given automorphism group.
Cite as

Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová. Temporal Valued Constraint Satisfaction Problems. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2025.24,
  author =	{Bodirsky, Manuel and Bonnet, \'{E}douard and Semani\v{s}inov\'{a}, \v{Z}aneta},
  title =	{{Temporal Valued Constraint Satisfaction Problems}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-241311},
  doi =		{10.4230/LIPIcs.MFCS.2025.24},
  annote =	{Keywords: Constraint Satisfaction Problems, valued CSPs, temporal CSPs, fractional polymorphisms, complexity dichotomy, min CSPs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.4
The Complexity of Boolean Surjective General-Valued CSPs

Authors: Peter Fulla and Stanislav Zivny

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity. In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for {0,infinity}-valued constraint languages corresponding to CSPs) obtained by Creignou and Hebrard, and the dichotomy for {0,1}-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.
Cite as

Peter Fulla and Stanislav Zivny. The Complexity of Boolean Surjective General-Valued CSPs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fulla_et_al:LIPIcs.MFCS.2017.4,
  author =	{Fulla, Peter and Zivny, Stanislav},
  title =	{{The Complexity of Boolean Surjective General-Valued CSPs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.4},
  URN =		{urn:nbn:de:0030-drops-80623},
  doi =		{10.4230/LIPIcs.MFCS.2017.4},
  annote =	{Keywords: constraint satisfaction problems, surjective CSP, valued CSP, min-cut, polymorphisms, multimorphisms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.39
On Planar Valued CSPs

Authors: Peter Fulla and Stanislav Zivny

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study the computational complexity of planar valued constraint satisfaction problems (VCSPs). First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of Dvorak and Kupec [ICALP'15] from CSPs to VCSPs. Second, we give a complete complexity classification of conservative planar VCSPs on arbitrary finite domains. As it turns out, in this case planarity does not lead to any new tractable cases, and thus our classification is a sharpening of the classification of conservative VCSPs by Kolmogorov and Zivny [JACM'13].
Cite as

Peter Fulla and Stanislav Zivny. On Planar Valued CSPs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fulla_et_al:LIPIcs.MFCS.2016.39,
  author =	{Fulla, Peter and Zivny, Stanislav},
  title =	{{On Planar Valued CSPs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.39},
  URN =		{urn:nbn:de:0030-drops-64537},
  doi =		{10.4230/LIPIcs.MFCS.2016.39},
  annote =	{Keywords: constraint satisfaction, valued constraint satisfaction, planarity, polymorphisms, multimorphisms}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2017
  • 1 2016

  • Refine by Author
  • 2 Fulla, Peter
  • 2 Zivny, Stanislav
  • 1 Bodirsky, Manuel
  • 1 Bonnet, Édouard
  • 1 Semanišinová, Žaneta

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Complexity theory and logic

  • Refine by Keyword
  • 2 multimorphisms
  • 2 polymorphisms
  • 1 Constraint Satisfaction Problems
  • 1 complexity dichotomy
  • 1 constraint satisfaction
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact