3 Search Results for "Lima, Carlos Vinícius G. C."

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.23
Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

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

Abstract
Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.
Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  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.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.7
Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion

Authors: Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.
Cite as

Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{morelle_et_al:LIPIcs.ESA.2025.7,
  author =	{Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.7},
  URN =		{urn:nbn:de:0030-drops-244751},
  doi =		{10.4230/LIPIcs.ESA.2025.7},
  annote =	{Keywords: Graph modification problems, Parameterized complexity, Graph minors, Flat Wall theorem, Irrelevant vertex technique, Algorithmic meta-theorem, Parametric dependence, Dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.12
Dual Parameterization of Weighted Coloring

Authors: Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Given a graph G, a proper k-coloring of G is a partition c = (S_i)_{i in [1,k]} of V(G) into k stable sets S_1,..., S_k. Given a weight function w: V(G) -> R^+, the weight of a color S_i is defined as w(i) = max_{v in S_i} w(v) and the weight of a coloring c as w(c) = sum_{i=1}^{k} w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G,w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n^{o(log n)} unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G,w) and an integer k, is sigma(G,w) <= sum_{v in V(G)} w(v) - k? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time 2^{O(k log k)} * n^{O(1)}, and asked which kernel size can be achieved for the problem. We provide an FPT algorithm running in time 9^k * n^{O(1)}, and prove that no algorithm in time 2^{o(k)} * n^{O(1)} exists under the ETH. On the other hand, we present a kernel with at most (2^{k-1}+1) (k-1) vertices, and rule out the existence of polynomial kernels unless NP subseteq coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Cite as

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva. Dual Parameterization of Weighted Coloring. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2018.12,
  author =	{Ara\'{u}jo, J\'{u}lio and Campos, Victor A. and Lima, Carlos Vin{\'\i}cius G. C. and Fernandes dos Santos, Vin{\'\i}cius and Sau, Ignasi and Silva, Ana},
  title =	{{Dual Parameterization of Weighted Coloring}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.12},
  URN =		{urn:nbn:de:0030-drops-102134},
  doi =		{10.4230/LIPIcs.IPEC.2018.12},
  annote =	{Keywords: weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2019

  • Refine by Author
  • 2 Sau, Ignasi
  • 1 Araújo, Júlio
  • 1 Campos, Victor A.
  • 1 Das, Arun Kumar
  • 1 Fernandes dos Santos, Vinícius
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Algorithmic meta-theorem
  • 1 Dynamic programming
  • 1 FPT
  • 1 FPT algorithms
  • 1 Flat Wall theorem
  • 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