4 Search Results for "Strømme, Torstein J. F."

Document
DOI: 10.4230/LIPIcs.IPEC.2025.31
Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard

Authors: Benjamin Bergougnoux and Lars Jaffke

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.
Cite as

Benjamin Bergougnoux and Lars Jaffke. Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 31:1-31:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.IPEC.2025.31,
  author =	{Bergougnoux, Benjamin and Jaffke, Lars},
  title =	{{Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{31:1--31:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.31},
  URN =		{urn:nbn:de:0030-drops-251631},
  doi =		{10.4230/LIPIcs.IPEC.2025.31},
  annote =	{Keywords: Hamiltonian Path, Hamiltonian Cycle, Mim-Width, Para-NP-Hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.25
Mim-Width Is paraNP-Complete

Authors: Benjamin Bergougnoux, Édouard Bonnet, and Julien Duron

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Width, and their linear counterparts are all paraNP-complete, i.e., NP-complete to compute even when upper bounded by a constant. A key intermediate problem that we introduce and show NP-complete, Linear Degree Balancing, inputs an edge-weighted graph G and an integer τ, and asks whether V(G) can be linearly ordered such that every vertex of G has weighted backward and forward degrees at most τ.
Cite as

Benjamin Bergougnoux, Édouard Bonnet, and Julien Duron. Mim-Width Is paraNP-Complete. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ICALP.2025.25,
  author =	{Bergougnoux, Benjamin and Bonnet, \'{E}douard and Duron, Julien},
  title =	{{Mim-Width Is paraNP-Complete}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.25},
  URN =		{urn:nbn:de:0030-drops-234020},
  doi =		{10.4230/LIPIcs.ICALP.2025.25},
  annote =	{Keywords: Mim-width, lower bounds, parameterized complexity, ordered graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.6
Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

Authors: Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle

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

Abstract
We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.
Cite as

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2018.6,
  author =	{Jaffke, Lars and Kwon, O-joung and Str{\o}mme, Torstein J. F. and Telle, Jan Arne},
  title =	{{Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-102074},
  doi =		{10.4230/LIPIcs.IPEC.2018.6},
  annote =	{Keywords: Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.21
Partial Complementation of Graphs

Authors: Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
A partial complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there a partial complement of G which is in G? We show that this problem can be solved in polynomial time for various choices of the graphs class G, such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of r-regular graphs.
Cite as

Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos. Partial Complementation of Graphs. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.SWAT.2018.21,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Str{\o}mme, Torstein J. F. and Thilikos, Dimitrios M.},
  title =	{{Partial Complementation of Graphs}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.21},
  URN =		{urn:nbn:de:0030-drops-88476},
  doi =		{10.4230/LIPIcs.SWAT.2018.21},
  annote =	{Keywords: Partial complementation, graph editing, graph classes}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2019
  • 1 2018

  • Refine by Author
  • 2 Bergougnoux, Benjamin
  • 2 Jaffke, Lars
  • 2 Strømme, Torstein J. F.
  • 1 Bonnet, Édouard
  • 1 Duron, Julien
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

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

  • Refine by Keyword
  • 1 Distance Domination Problems
  • 1 Graph Classes
  • 1 Graph Width Parameters
  • 1 Hamiltonian Cycle
  • 1 Hamiltonian Path
  • 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