3 Search Results for "Aboulker, Pierre"


Document
Grundy Coloring & Friends, Half-Graphs, Bicliques

Authors: Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order σ, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering σ, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force f(k)n^{2^{k-1}}-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K_{t,t}-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.

Cite as

Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy Coloring & Friends, Half-Graphs, Bicliques. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 58:1-58:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{aboulker_et_al:LIPIcs.STACS.2020.58,
  author =	{Aboulker, Pierre and Bonnet, \'{E}douard and Kim, Eun Jung and Sikora, Florian},
  title =	{{Grundy Coloring \& Friends, Half-Graphs, Bicliques}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.58},
  URN =		{urn:nbn:de:0030-drops-119190},
  doi =		{10.4230/LIPIcs.STACS.2020.58},
  annote =	{Keywords: Grundy coloring, parameterized complexity, ETH lower bounds, K\underline\{t,t\}-free graphs, half-graphs}
}
Document
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

Authors: Christian Konrad and Viktor Zamaraev

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We give deterministic distributed (1+epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.

Cite as

Christian Konrad and Viktor Zamaraev. Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.MFCS.2019.21,
  author =	{Konrad, Christian and Zamaraev, Viktor},
  title =	{{Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.21},
  URN =		{urn:nbn:de:0030-drops-109651},
  doi =		{10.4230/LIPIcs.MFCS.2019.21},
  annote =	{Keywords: local model, approximation algorithms, minimum vertex coloring, maximum independent set, chordal graphs}
}
Document
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs

Authors: Lars Jaffke and Paloma T. Lima

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors. The b-chromatic number of a graph G, denoted by chi_b(G), is the maximum number k such that G admits a b-coloring with k colors. We consider the complexity of the b-Coloring problem, whenever the value of k is close to one of two upper bounds on chi_b(G): The maximum degree Delta(G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i-1. We obtain a dichotomy result for all fixed k in N when k is close to one of the two above mentioned upper bounds. Concretely, we show that if k in {Delta(G) + 1 - p, m(G) - p}, the problem is polynomial-time solvable whenever p in {0, 1} and, even when k = 3, it is NP-complete whenever p >= 2. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Delta(G) of the input graph G and give two FPT-algorithms. First, we show that deciding whether a graph G has a b-coloring with m(G) colors is FPT parameterized by Delta(G). Second, we show that b-Coloring{} is FPT parameterized by Delta(G) + l_k(G), where l_k(G) denotes the number of vertices of degree at least k.

Cite as

Lars Jaffke and Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2019.34,
  author =	{Jaffke, Lars and Lima, Paloma T.},
  title =	{{A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.34},
  URN =		{urn:nbn:de:0030-drops-109784},
  doi =		{10.4230/LIPIcs.MFCS.2019.34},
  annote =	{Keywords: b-Coloring, b-Chromatic Number}
}
  • Refine by Author
  • 1 Aboulker, Pierre
  • 1 Bonnet, Édouard
  • 1 Jaffke, Lars
  • 1 Kim, Eun Jung
  • 1 Konrad, Christian
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph coloring
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 ETH lower bounds
  • 1 Grundy coloring
  • 1 K_{t,t}-free graphs
  • 1 approximation algorithms
  • 1 b-Chromatic Number
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail