2 Search Results for "Lonc, Zbigniew"


Document
Coloring and Recognizing Mixed Interval Graphs

Authors: Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

Cite as

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36,
  author =	{Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes},
  title =	{{Coloring and Recognizing Mixed Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36},
  URN =		{urn:nbn:de:0030-drops-193388},
  doi =		{10.4230/LIPIcs.ISAAC.2023.36},
  annote =	{Keywords: Interval Graphs, Mixed Graphs, Graph Coloring}
}
Document
Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws

Authors: Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring. We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex. As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations: 1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs

Cite as

Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14,
  author =	{D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.14},
  URN =		{urn:nbn:de:0030-drops-172996},
  doi =		{10.4230/LIPIcs.ISAAC.2022.14},
  annote =	{Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension}
}
  • Refine by Author
  • 2 Rzążewski, Paweł
  • 1 Dębski, Michał
  • 1 Gutowski, Grzegorz
  • 1 Junosza-Szaniawski, Konstanty
  • 1 Klesen, Felix
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Graph Coloring
  • 1 Interval Graphs
  • 1 Mixed Graphs
  • 1 forbidden induced subgraphs
  • 1 graph homomorphism
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

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