5 Search Results for "Madelaine, Florent R."

Document
DOI: 10.4230/LIPIcs.CSL.2026.41
Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide

Authors: Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, and Florent Madelaine

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. We prove that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide.
Cite as

Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, and Florent Madelaine. Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.CSL.2026.41,
  author =	{Ghasemi, Fatemeh and Grange, Julien and Kant\'{e}, Mamadou Moustapha and Madelaine, Florent},
  title =	{{Weakly-Sparse and Strongly Flip-Flat Classes of Graphs Are Uniformly Almost-Wide}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.41},
  URN =		{urn:nbn:de:0030-drops-254668},
  doi =		{10.4230/LIPIcs.CSL.2026.41},
  annote =	{Keywords: Almost-wide, Flip-flatness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.83
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Authors: Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess

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

Abstract
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. We provide answers to three fundamental questions on the scope of the Bodirsky-Pinsker conjecture. Our first two main results provide two simplifications of this scope, one of structural, and the other one of algebraic nature. The former simplification implies that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in the most powerful classification methods. The latter yields that the higher-arity invariants of any template within its scope can be assumed to be essentially injective, and any algebraic condition characterizing any complexity class within the conjecture closed under Datalog reductions must be satisfiable by injections, thus lifting the mystery of the better applicability of certain conditions over others. Our third main result uses the first one to show that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification of it, as the witness of the tractability of a non-finitely tractable finite-domain Promise Constraint Satisfaction Problem (PCSP) by the so-called sandwich method. This generalizes a recent result of Mottet and provides a strong hitherto unknown connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs.
Cite as

Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess. Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pinsker_et_al:LIPIcs.MFCS.2025.83,
  author =	{Pinsker, Michael and Rydval, Jakub and Sch\"{o}bi, Moritz and Spiess, Christoph},
  title =	{{Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{83:1--83:20},
  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.83},
  URN =		{urn:nbn:de:0030-drops-241903},
  doi =		{10.4230/LIPIcs.MFCS.2025.83},
  annote =	{Keywords: (Promise) Constraint Satisfaction Problem, dichotomy conjecture, polymorphism, identity, algebraicity, homogeneity, \omega-categoricity, finite boundedness, Datalog}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.158
Restricted CSPs and F-Free Digraph Algorithmics

Authors: Santiago Guzmán-Pro and Barnaby Martin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.
Cite as

Santiago Guzmán-Pro and Barnaby Martin. Restricted CSPs and F-Free Digraph Algorithmics. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 158:1-158:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guzmanpro_et_al:LIPIcs.ICALP.2025.158,
  author =	{Guzm\'{a}n-Pro, Santiago and Martin, Barnaby},
  title =	{{Restricted CSPs and F-Free Digraph Algorithmics}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{158:1--158:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.158},
  URN =		{urn:nbn:de:0030-drops-235352},
  doi =		{10.4230/LIPIcs.ICALP.2025.158},
  annote =	{Keywords: Digraph homomorphisms, constraint satisfaction problems, subgraph-free algorithmics}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.140
Containment for Guarded Monotone Strict NP

Authors: Alexey Barsukov, Michael Pinsker, and Jakub Rydval

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment problem for GMSNP is decidable, thereby settling an open question of Bienvenu, ten Cate, Lutz, and Wolter, later restated by Bourhis and Lutz. Our proof also comes with a 2NEXPTIME upper bound on the complexity of the problem, which matches the lower bound for containment of MMSNP due to Bourhis and Lutz. In order to obtain these results, we significantly improve the state of knowledge of the model-theoretic properties of GMSNP. Bodirsky, Knäuer, and Starke previously showed that every GMSNP sentence defines a finite union of CSPs of ω-categorical structures. We show that these structures can be used to obtain a reduction from the containment problem for GMSNP to the much simpler problem of testing the existence of a certain map called recolouring, albeit in a more general setting than GMSNP; a careful analysis of this yields said upper bound. As a secondary contribution, we refine the construction of Bodirsky, Knäuer, and Starke by adding a restricted form of homogeneity to the properties of these structures, making the logic amenable to future complexity classifications for query evaluation using techniques developed for infinite-domain CSPs.
Cite as

Alexey Barsukov, Michael Pinsker, and Jakub Rydval. Containment for Guarded Monotone Strict NP. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 140:1-140:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barsukov_et_al:LIPIcs.ICALP.2025.140,
  author =	{Barsukov, Alexey and Pinsker, Michael and Rydval, Jakub},
  title =	{{Containment for Guarded Monotone Strict NP}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{140:1--140:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.140},
  URN =		{urn:nbn:de:0030-drops-235176},
  doi =		{10.4230/LIPIcs.ICALP.2025.140},
  annote =	{Keywords: guarded, monotone, SNP, forbidden patterns, query containment, recolouring, decidability, computational complexity, \omega-categoricity, constraint satisfaction, homogeneity, amalgamation property, Ramsey property, canonical function}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.11
Consistency for Counting Quantifiers

Authors: Florent R. Madelaine and Barnaby Martin

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard.
Cite as

Florent R. Madelaine and Barnaby Martin. Consistency for Counting Quantifiers. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{madelaine_et_al:LIPIcs.MFCS.2018.11,
  author =	{Madelaine, Florent R. and Martin, Barnaby},
  title =	{{Consistency for Counting Quantifiers}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.11},
  URN =		{urn:nbn:de:0030-drops-95931},
  doi =		{10.4230/LIPIcs.MFCS.2018.11},
  annote =	{Keywords: Quantified Constraints, Constraint Satisfaction, Logic in Computer Science, Universal Algebra, Computational Complexity}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2018

  • Refine by Author
  • 2 Martin, Barnaby
  • 2 Pinsker, Michael
  • 2 Rydval, Jakub
  • 1 Barsukov, Alexey
  • 1 Ghasemi, Fatemeh
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Logic
  • 2 Theory of computation → Computational complexity and cryptography
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Constraint and logic programming
  • Show More...

  • Refine by Keyword
  • 2 homogeneity
  • 2 ω-categoricity
  • 1 (Promise) Constraint Satisfaction Problem
  • 1 Almost-wide
  • 1 Computational Complexity
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact