3 Search Results for "Mannens, Isja"


Document
The Parameterised Complexity Of Integer Multicommodity Flow

Authors: Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters. In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter.

Cite as

Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen. The Parameterised Complexity Of Integer Multicommodity Flow. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.6,
  author =	{Bodlaender, Hans L. and Mannens, Isja and Oostveen, Jelle J. and Pandey, Sukanya and van Leeuwen, Erik Jan},
  title =	{{The Parameterised Complexity Of Integer Multicommodity Flow}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.6},
  URN =		{urn:nbn:de:0030-drops-194250},
  doi =		{10.4230/LIPIcs.IPEC.2023.6},
  annote =	{Keywords: multicommodity flow, parameterised complexity, XNLP-completeness, XALP-completeness}
}
Document
A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth

Authors: Isja Mannens and Jesper Nederlof

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
We give a fine-grained classification of evaluating the Tutte polynomial T(G;x,y) on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any point (x,y) ∈ ℤ² that either - T(G; x, y) can be computed in polynomial time, - T(G; x, y) can be computed in 2^O(tw) n^O(1) time, but not in 2^o(ctw) n^O(1) time assuming the Exponential Time Hypothesis (ETH), - T(G; x, y) can be computed in 2^O(tw log tw) n^O(1) time, but not in 2^o(ctw log ctw) n^O(1) time assuming the ETH, where we assume tree decompositions of treewidth tw and cutwidth decompositions of cutwidth ctw are given as input along with the input graph on n vertices and point (x,y). To obtain these results, we refine the existing reductions that were instrumental for the seminal dichotomy by Jaeger, Welsh and Vertigan [Math. Proc. Cambridge Philos. Soc'90]. One of our technical contributions is a new rank bound of a matrix that indicates whether the union of two forests is a forest itself, which we use to show that the number of forests of a graph can be counted in 2^O(tw) n^O(1) time.

Cite as

Isja Mannens and Jesper Nederlof. A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{mannens_et_al:LIPIcs.ESA.2023.82,
  author =	{Mannens, Isja and Nederlof, Jesper},
  title =	{{A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{82:1--82:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.82},
  URN =		{urn:nbn:de:0030-drops-187354},
  doi =		{10.4230/LIPIcs.ESA.2023.82},
  annote =	{Keywords: Width Parameters, Parameterized Complexity, Tutte Polynomial}
}
Document
Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Authors: Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small edge separators. Let p,q ∈ ℕ such that p is a prime and q ≥ 3. We show: - If p divides q-1, there is a (q-1)^{ctw}n^{O(1)} time algorithm for counting list q-colorings modulo p of n-vertex graphs of cutwidth ctw. Furthermore, there is no ε > 0 for which there is a (q-1-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming the Strong Exponential Time Hypothesis (SETH). - If p does not divide q-1, there is no ε > 0 for which there exists a (q-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming SETH. The lower bounds are in stark contrast with the existing 2^{ctw}n^{O(1)} time algorithm to compute the chromatic number of a graph by Jansen and Nederlof [Theor. Comput. Sci.'18]. Furthermore, by building upon the above lower bounds, we obtain the following lower bound for counting connected spanning edge sets: there is no ε > 0 for which there is an algorithm that, given a graph G and a cutwidth ordering of cutwidth ctw, counts the number of spanning connected edge sets of G modulo p in time (p - ε)^{ctw} n^{O(1)}, assuming SETH. We also give an algorithm with matching running time for this problem. Before our work, even for the treewidth parameterization, the best conditional lower bound by Dell et al. [ACM Trans. Algorithms'14] only excluded 2^{o(tw)}n^{O(1)} time algorithms for this problem. Both our algorithms and lower bounds employ use of the matrix rank method, by relating the complexity of the problem to the rank of a certain "compatibility matrix" in a non-trivial way.

Cite as

Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.STACS.2022.36,
  author =	{Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Szil\'{a}gyi, Krisztina},
  title =	{{Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.36},
  URN =		{urn:nbn:de:0030-drops-158464},
  doi =		{10.4230/LIPIcs.STACS.2022.36},
  annote =	{Keywords: connected edge sets, cutwidth, parameterized algorithms, colorings, counting modulo p}
}
  • Refine by Author
  • 3 Mannens, Isja
  • 2 Nederlof, Jesper
  • 1 Bodlaender, Hans L.
  • 1 Groenland, Carla
  • 1 Oostveen, Jelle J.
  • Show More...

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

  • Refine by Keyword
  • 1 Parameterized Complexity
  • 1 Tutte Polynomial
  • 1 Width Parameters
  • 1 XALP-completeness
  • 1 XNLP-completeness
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2023
  • 1 2022

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