Search Results

Documents authored by de Vlas, Jorke M.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.120
Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables

Authors: Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas, and Magnus Wahlström

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study connections between parameterized complexity, universal algebra, and structural graph parameters. Our starting point is the constraint satisfaction problem over instances with few variables but unbounded domain size (udCSP). Surprisingly, many upper and lower bounds in parameterized complexity can be expressed as solving such udCSPs. Prominent examples include the FPT algorithms for Boolean MinCSP [Eun Jung Kim et al., 2025], Directed Multicut with three cut requests [Meike Hatzel et al., 2023], and the canonical W[1]-hardness construction Paired Min Cut [Dániel Marx and Igor Razgon, 2009]. We represent constraints over unbounded domains by a set of unary maps ℳ into a finite base language Γ, situating udCSP(Γ, ℳ) in the algebraic terra incognita between finite and infinite domains. We present a novel algebraic theory that explains the parameterized complexity of problems such as Paired Min Cut, 𝓁-Chain Sat, and Coupled Min Cut, and unifies disparate FPT algorithms through the lens of twin-width. In particular, we simplify key steps in existing algorithms, e.g., for Boolean MinCSP, via a clean reduction to udCSP. We specifically concentrate on udCSP(Γ,ℳ) restricted to monotone maps Mo, where we identify the crucial connector polymorphism: its presence implies FPT for binary relations (via dynamic programming based on twin-width), while its absence entails W[1]-hardness. Extending this to higher-arity relations is related to the notoriously difficult task of finding a generalisation of twin-width to non-binary structures. As a step in this direction, inspired by our algebraic framework, we introduce a new structural parameter, projected grid-rank, and show that it coincides with the connector property, and agrees with twin-width for binary structures. More strongly, we show that for structures of bounded arity and bounded projected grid-rank, all binary projections have bounded twin-width. This width measure may thus be of independent interest for any problem currently hinging on generalizations of twin-width.
Cite as

Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas, and Magnus Wahlström. Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jonsson_et_al:LIPIcs.ICALP.2026.120,
  author =	{Jonsson, Peter and Lagerkvist, Victor and de Vlas, Jorke M. and Wahlstr\"{o}m, Magnus},
  title =	{{Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{120:1--120:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.120},
  URN =		{urn:nbn:de:0030-drops-265092},
  doi =		{10.4230/LIPIcs.ICALP.2026.120},
  annote =	{Keywords: Constraint satisfaction problems, parameterized complexity, twin-width, universal algebra}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.35
On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper)

Authors: Jorke M. de Vlas

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
We give a polynomial time algorithm that solves a CSP over 𝐙 with linear inequalities of the form c^{a₁} x - c^{a₂} y ≤ b where x and y are variables, a₁, a₂ and b are parameters, and c is a fixed constant. This is a step in classifying the complexity of CSP(Γ) for first-order reducts Γ from (𝐙, < ,+,1). The algorithm works by first reducing the infinite domain to a finite domain by inferring an upper bound on the size of the smallest solution, then repeatedly merging consecutive constraints into new constraints, and finally solving the problem using arc consistency.
Cite as

Jorke M. de Vlas. On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 35:1-35:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{devlas:LIPIcs.CP.2024.35,
  author =	{de Vlas, Jorke M.},
  title =	{{On the Complexity of Integer Programming with Fixed-Coefficient Scaling}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{35:1--35:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.35},
  URN =		{urn:nbn:de:0030-drops-207203},
  doi =		{10.4230/LIPIcs.CP.2024.35},
  annote =	{Keywords: constraint satisfaction problems, integer programming, CSP dichotomy}
}
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