2 Search Results for "Alferov, Vasily"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.5
Graph Coloring Below Guarantees via Co-Triangle Packing

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the 𝓁-Coloring problem, we are given a graph on n nodes, and tasked with determining if its vertices can be properly colored using 𝓁 colors. In this paper we study below-guarantee graph coloring, which tests whether an n-vertex graph can be properly colored using g-k colors, where g is a trivial upper bound such as n. We introduce an algorithmic framework that builds on a packing of co-triangles K₃ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return yes; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved 𝓁-Coloring (for any 𝓁) in randomized O^∗(2^k) time when given a K₂-free modulator of size k, we show that this problem can likewise be solved in randomized O^*(2^{k}) time when given a K₃-free modulator of size k. This result in turn yields a randomized O^*(2^{3k/2}) algorithm for (n-k)-Coloring (also known as Dual Coloring), improving the previous O^*(4^k) bound. We then introduce a smaller parameterization, (ω+μ-k)-Coloring, where ω is the clique number and μ is the size of a maximum matching in the complement graph; since ω+μ ≤ n for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized O^*(2^{6k}) algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for (ω-k)-Coloring or (μ-k)-Coloring under standard complexity assumptions.
Cite as

Shyan Akmal and Tomohiro Koana. Graph Coloring Below Guarantees via Co-Triangle Packing. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ISAAC.2025.5,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Graph Coloring Below Guarantees via Co-Triangle Packing}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.5},
  URN =		{urn:nbn:de:0030-drops-249130},
  doi =		{10.4230/LIPIcs.ISAAC.2025.5},
  annote =	{Keywords: coloring, parameterized algorithms, algebraic algorithms, above-guarantee, below-guarantee, subset convolution, determinants}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.18
On the Satisfiability of Smooth Grid CSPs

Authors: Vasily Alferov and Mateus de Oliveira Oliveira

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of grid CSPs by analyzing, from an experimental perspective, a symbolic parameter called smoothness. More specifically, we implement an algorithm that provably works in polynomial time on grids of polynomial smoothness. Subsequently, we compare our algorithm with standard combinatorial optimization techniques, such as SAT-solving and integer linear programming (ILP). For this comparison, we use a class of grid-CSPs encoding the pigeonhole principle. We demonstrate, empirically, that these CSPs have polynomial smoothness and that our algorithm terminates in polynomial time. On the other hand, as strong evidence that the grid-like encoding is not destroying the essence of the pigeonhole principle, we show that the standard propositional translation of pigeonhole CSPs remains hard for state-of-the-art SAT solvers, such as minisat and glucose, and even to state-of-the-art integer linear-programming solvers, such as Coin-OR CBC.
Cite as

Vasily Alferov and Mateus de Oliveira Oliveira. On the Satisfiability of Smooth Grid CSPs. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alferov_et_al:LIPIcs.SEA.2022.18,
  author =	{Alferov, Vasily and de Oliveira Oliveira, Mateus},
  title =	{{On the Satisfiability of Smooth Grid CSPs}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.18},
  URN =		{urn:nbn:de:0030-drops-165526},
  doi =		{10.4230/LIPIcs.SEA.2022.18},
  annote =	{Keywords: Grid CSPs, Smoothness, SAT Solving, Linear Programming}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022

  • Refine by Author
  • 1 Akmal, Shyan
  • 1 Alferov, Vasily
  • 1 Koana, Tomohiro
  • 1 de Oliveira Oliveira, Mateus

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Grid CSPs
  • 1 Linear Programming
  • 1 SAT Solving
  • 1 Smoothness
  • 1 above-guarantee
  • 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