23 Search Results for "Wahlström, Magnus"

Volume

LIPIcs, Volume 285

18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands

Editors: Neeldhara Misra and Magnus Wahlström

Document
DOI: 10.4230/LIPIcs.STACS.2025.52
Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion

Authors: Séhane Bel Houari-Durand, Eduard Eiben, and Magnus Wahlström

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Given a graph G and an integer k, the H-free Edge Deletion problem asks whether there exists a set of at most k edges of G whose deletion makes G free of induced copies of H. Significant attention has been given to the kernelizability aspects of this problem - i.e., for which graphs H does the problem admit an "efficient preprocessing" procedure, known as a polynomial kernelization, where an instance I of the problem with parameter k is reduced to an equivalent instance I' whose size and parameter value are bounded polynomially in k? Although such routines are known for many graphs H where the class of H-free graphs has significant restricted structure, it is also clear that for most graphs H the problem is incompressible, i.e., admits no polynomial kernelization parameterized by k unless the polynomial hierarchy collapses. These results led Marx and Sandeep to the conjecture that H-free Edge Deletion is incompressible for any graph H with at least five vertices, unless H is complete or has at most one edge (JCSS 2022). This conjecture was reduced to the incompressibility of H-free Edge Deletion for a finite list of graphs H. We consider one of these graphs, which we dub the prison, and show that Prison-Free Edge Deletion has a polynomial kernel, refuting the conjecture. On the other hand, the same problem for the complement of the prison is incompressible.
Cite as

Séhane Bel Houari-Durand, Eduard Eiben, and Magnus Wahlström. Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{houaridurand_et_al:LIPIcs.STACS.2025.52,
  author =	{Houari-Durand, S\'{e}hane Bel and Eiben, Eduard and Wahlstr\"{o}m, Magnus},
  title =	{{Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.52},
  URN =		{urn:nbn:de:0030-drops-228770},
  doi =		{10.4230/LIPIcs.STACS.2025.52},
  annote =	{Keywords: Graph modification problems, parameterized complexity, polynomial kernelization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.62
Faster Algorithms on Linear Delta-Matroids

Authors: Tomohiro Koana and Magnus Wahlström

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We present new algorithms and constructions for linear delta-matroids. Delta-matroids are generalizations of matroids that also capture structures such as matchable vertex sets in graphs and path-packing problems. As with matroids, an important class of delta-matroids is given by linear delta-matroids, which generalize linear matroids and are represented via a "twist" of a skew-symmetric matrix. We observe an alternative representation, termed a contraction representation over a skew-symmetric matrix. This representation is equivalent to the more standard twist representation up to O(n^ω)-time transformations (where n is the dimension of the delta-matroid and ω < 2.372 the matrix multiplication exponent), but it is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions for linear delta-matroids. In particular, we show that the union and delta-sum of linear delta-matroids are again linear delta-matroids, and that a representation for the resulting delta-matroid can be constructed in randomized time O(n^ω) (or more precisely, in O(n^ω) field operations, over a field of size at least Ω(n⋅(1/ε)), where ε > 0 is an error parameter). Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single O(n^ω)-time matrix rank computation. Using the methods of Harvey, previously applied by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the O(n⁴)-time augmenting path algorithm of Geelen, Iwata and Murota, albeit with randomization. Finally, we consider the maximum-cardinality delta-matroid intersection problem (equivalently, the maximum-cardinality delta-matroid matching problem). Using Storjohann’s algorithms for symbolic determinants, we show that such a solution can be found in O(n^{ω+1}) time. This provides the first (randomized) polynomial-time solution for the problem, thereby solving an open question of Kakimura and Takamatsu.
Cite as

Tomohiro Koana and Magnus Wahlström. Faster Algorithms on Linear Delta-Matroids. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2025.62,
  author =	{Koana, Tomohiro and Wahlstr\"{o}m, Magnus},
  title =	{{Faster Algorithms on Linear Delta-Matroids}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.62},
  URN =		{urn:nbn:de:0030-drops-228876},
  doi =		{10.4230/LIPIcs.STACS.2025.62},
  annote =	{Keywords: Delta-matroids, Randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.93
Parameterized Complexity of MinCSP over the Point Algebra

Authors: George Osipov, Marcin Pilipczuk, and Magnus Wahlström

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form x < y, x = y, x ≤ y and x ≠ y, and a budget k. The goal is to check whether it is possible to assign rational values to the variables while breaking constraints of total cost at most k. This problem generalizes several prominent graph separation and transversal problems: - MinCSP({<}) is equivalent to Directed Feedback Arc Set, - MinCSP({< , ≤}) is equivalent to Directed Subset Feedback Arc Set, - MinCSP({= ,≠}) is equivalent to Edge Multicut, and - MinCSP({≤ ,≠}) is equivalent to Directed Symmetric Multicut. Apart from trivial cases, MinCSP({Γ}) for Γ ⊆ {< , = , ≤ ,≠} is NP-hard even to approximate within any constant factor under the Unique Games Conjecture. Hence, we study parameterized complexity of this problem under a natural parameterization by the solution cost k. We obtain a complete classification: if Γ ⊆ {< , = , ≤ ,≠} contains both ≤ and ≠, then MinCSP({Γ}) is W[1]-hard, otherwise it is fixed-parameter tractable. For the positive cases, we solve MinCSP({< , = ,≠}), generalizing the FPT results for Directed Feedback Arc Set and Edge Multicut as well as their weighted versions. Our algorithm works by reducing the problem into a Boolean MinCSP, which is in turn solved by flow augmentation. For the lower bounds, we prove that Directed Symmetric Multicut is W[1]-hard, solving an open problem.
Cite as

George Osipov, Marcin Pilipczuk, and Magnus Wahlström. Parameterized Complexity of MinCSP over the Point Algebra. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{osipov_et_al:LIPIcs.ESA.2024.93,
  author =	{Osipov, George and Pilipczuk, Marcin and Wahlstr\"{o}m, Magnus},
  title =	{{Parameterized Complexity of MinCSP over the Point Algebra}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{93:1--93:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.93},
  URN =		{urn:nbn:de:0030-drops-211640},
  doi =		{10.4230/LIPIcs.ESA.2024.93},
  annote =	{Keywords: parameterized complexity, constraint satisfaction, point algebra, multicut, feedback arc set}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.148
An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs

Authors: Antoine Mottet, Tomáš Nagy, and Michael Pinsker

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC'11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP'16) on graph satisfiability.
Cite as

Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael},
  title =	{{An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{148:1--148:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.148},
  URN =		{urn:nbn:de:0030-drops-202912},
  doi =		{10.4230/LIPIcs.ICALP.2024.148},
  annote =	{Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.IPEC.2023
LIPIcs, Volume 285, IPEC 2023, Complete Volume

Authors: Neeldhara Misra and Magnus Wahlström

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

Abstract
LIPIcs, Volume 285, IPEC 2023, Complete Volume
Cite as

18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{misra_et_al:LIPIcs.IPEC.2023,
  title =	{{LIPIcs, Volume 285, IPEC 2023, Complete Volume}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{1--644},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023},
  URN =		{urn:nbn:de:0030-drops-194183},
  doi =		{10.4230/LIPIcs.IPEC.2023},
  annote =	{Keywords: LIPIcs, Volume 285, IPEC 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.IPEC.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Neeldhara Misra and Magnus Wahlström

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.IPEC.2023.0,
  author =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{0:i--0:xviii},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.0},
  URN =		{urn:nbn:de:0030-drops-194191},
  doi =		{10.4230/LIPIcs.IPEC.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.86
Parameterized Complexity of Equality MinCSP

Authors: George Osipov and Magnus Wahlström

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

Abstract
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as ℕ, where the relations are defined via first-order formulas whose only predicate is =. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP(Γ) for every finite equality language Γ, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the "cut requests" come as disjunctions over O(1) individual cut requests s_i ≠ t_i. We also consider singleton expansions of equality languages, enriching an equality language with the capability for assignment constraints (x = i) for either a finite or infinitely many constants i, and fully characterize the complexity of the resulting MinCSP.
Cite as

George Osipov and Magnus Wahlström. Parameterized Complexity of Equality MinCSP. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 86:1-86:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{osipov_et_al:LIPIcs.ESA.2023.86,
  author =	{Osipov, George and Wahlstr\"{o}m, Magnus},
  title =	{{Parameterized Complexity of Equality MinCSP}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{86:1--86: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.86},
  URN =		{urn:nbn:de:0030-drops-187393},
  doi =		{10.4230/LIPIcs.ESA.2023.86},
  annote =	{Keywords: parameterized complexity, constraint satisfaction, parameterized approximation}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.11
On the Parameterized Complexity of Symmetric Directed Multicut

Authors: Eduard Eiben, Clément Rambaud, and Magnus Wahlström

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph D, a set of cut requests C = {(s₁,t₁),…,(s_l,t_l)} and an integer k, and the task is to find a set X ⊆ V(D) of size at most k such that for every 1 ≤ i ≤ l, X intersects either all (s_i,t_i)-paths or all (t_i,s_i)-paths. Equivalently, every strongly connected component of D-X contains at most one vertex out of s_i and t_i for every i. This problem is previously known from research in approximation algorithms, where it is known to have an O(log k log log k)-approximation. We note that the problem, parameterized by k, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by k, but we give three partial results: An FPT algorithm parameterized by k+l; an FPT-time 2-approximation parameterized by k; and an FPT algorithm parameterized by k for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by k remains an intriguing open possibility.
Cite as

Eduard Eiben, Clément Rambaud, and Magnus Wahlström. On the Parameterized Complexity of Symmetric Directed Multicut. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.IPEC.2022.11,
  author =	{Eiben, Eduard and Rambaud, Cl\'{e}ment and Wahlstr\"{o}m, Magnus},
  title =	{{On the Parameterized Complexity of Symmetric Directed Multicut}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.11},
  URN =		{urn:nbn:de:0030-drops-173679},
  doi =		{10.4230/LIPIcs.IPEC.2022.11},
  annote =	{Keywords: Parameterized complexity, directed graphs, graph separation problems}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.4
A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

Authors: Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.
Cite as

Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4,
  author =	{Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi},
  title =	{{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4},
  URN =		{urn:nbn:de:0030-drops-153879},
  doi =		{10.4230/LIPIcs.IPEC.2021.4},
  annote =	{Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.52
Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

Authors: Zhiyang He, Jason Li, and Magnus Wahlström

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Let G be a graph and S, T ⊆ V(G) be (possibly overlapping) sets of terminals, |S| = |T| = k. We are interested in computing a vertex sparsifier for terminal cuts in G, i.e., a graph H on a smallest possible number of vertices, where S ∪ T ⊆ V(H) and such that for every A ⊆ S and B ⊆ T the size of a minimum (A,B)-vertex cut is the same in G as in H. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlström (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier H with O(k³) vertices can be computed in randomized polynomial time, even for arbitrary digraphs G. However, since then, no improvements on the size O(k³) have been shown. In this paper, we draw inspiration from the renowned Bollobás’s Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlström’s methods. This new perspective allows us to construct a sparsifier H of Θ(k²) vertices for the case that G is a DAG. We also show how to compute H in time near-linear in the size of G, improving on the previous O(n^{ω+1}). Furthermore, H recovers the closest min-cut in G for every partition (A,B), which was not previously known. Finally, we show that a sparsifier of size Ω(k²) is required, both for DAGs and for undirected edge cuts.
Cite as

Zhiyang He, Jason Li, and Magnus Wahlström. Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ESA.2021.52,
  author =	{He, Zhiyang and Li, Jason and Wahlstr\"{o}m, Magnus},
  title =	{{Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.52},
  URN =		{urn:nbn:de:0030-drops-146331},
  doi =		{10.4230/LIPIcs.ESA.2021.52},
  annote =	{Keywords: graph theory, vertex sparsifier, representative family, matroid}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.2
Component Order Connectivity in Directed Graphs

Authors: Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlström, and Anders Yeo

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
A directed graph D is semicomplete if for every pair x,y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V,A) and a pair of natural numbers k and 𝓁, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D-X has at most 𝓁 vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for 𝓁 = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, 𝓁, 𝓁+k and n-𝓁. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^*(2^(16k)) but not in time O^*(2^o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^*(2^(16k)) implies the upper bound O^*(2^(16(n-𝓁))) for the parameter n-𝓁. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n-𝓁)) unless ETH fails. Finally, we improve (in dependency on 𝓁) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter 𝓁+k on general digraphs from O^*(2^O(k𝓁 log (k𝓁))) to O^*(2^O(klog (k𝓁))). Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^*(2^o(klog 𝓁)) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).
Cite as

Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlström, and Anders Yeo. Component Order Connectivity in Directed Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bangjensen_et_al:LIPIcs.IPEC.2020.2,
  author =	{Bang-Jensen, J{\o}rgen and Eiben, Eduard and Gutin, Gregory and Wahlstr\"{o}m, Magnus and Yeo, Anders},
  title =	{{Component Order Connectivity in Directed Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.2},
  URN =		{urn:nbn:de:0030-drops-133058},
  doi =		{10.4230/LIPIcs.IPEC.2020.2},
  annote =	{Keywords: Parameterized Algorithms, component order connectivity, directed graphs, semicomplete digraphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.66
Many Visits TSP Revisited

Authors: Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study the Many Visits TSP problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O*(5ⁿ). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results: - A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ε)-approximation in time O*(2ⁿε^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2ⁿ)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. - A tight analysis of Berger et al.’s exponential space algorithm, resulting in an O*(4ⁿ) running time bound. - A new polynomial space algorithm, running in time O(7.88ⁿ).
Cite as

Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström. Many Visits TSP Revisited. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.ESA.2020.66,
  author =	{Kowalik, {\L}ukasz and Li, Shaohua and Nadara, Wojciech and Smulewicz, Marcin and Wahlstr\"{o}m, Magnus},
  title =	{{Many Visits TSP Revisited}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{66:1--66:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.66},
  URN =		{urn:nbn:de:0030-drops-129329},
  doi =		{10.4230/LIPIcs.ESA.2020.66},
  annote =	{Keywords: many visits traveling salesman problem, exponential algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.11
Solving Packing Problems with Few Small Items Using Rainbow Matchings

Authors: Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, and Malte Skambath

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no "small" items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4^k⋅ k!⋅ n^{O(1)}. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Covering with run time O((k!)² ⋅ k ⋅ 2^k ⋅ n log(n)).
Cite as

Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, and Malte Skambath. Solving Packing Problems with Few Small Items Using Rainbow Matchings. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.MFCS.2020.11,
  author =	{Bannach, Max and Berndt, Sebastian and Maack, Marten and Mnich, Matthias and Lassota, Alexandra and Rau, Malin and Skambath, Malte},
  title =	{{Solving Packing Problems with Few Small Items Using Rainbow Matchings}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.11},
  URN =		{urn:nbn:de:0030-drops-126816},
  doi =		{10.4230/LIPIcs.MFCS.2020.11},
  annote =	{Keywords: Bin Packing, Knapsack, matching, fixed-parameter tractable}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.101
On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems

Authors: Magnus Wahlström

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We show the existence of an exact mimicking network of k^O(log k) edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than Θ(log n), then a mimicking network of quasipolynomial size can be computed in polynomial time. As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, 0-Extension for integer-weighted metrics, and Edge Multicut parameterized by the solution and the number of cut requests. The result works via a combination of the matroid-based irrelevant edge approach used in the kernel for s-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. The main technical contribution is a matroid-based marking procedure that we can show will mark all non-irrelevant edges, assuming that the graph is sufficiently densely connected. The only part of the result that is not currently constructive and polynomial-time computable is the detection of such sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for s-Multiway Cut for constant value of s (Kratsch and Wahlström, FOCS 2012).
Cite as

Magnus Wahlström. On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wahlstrom:LIPIcs.ICALP.2020.101,
  author =	{Wahlstr\"{o}m, Magnus},
  title =	{{On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.101},
  URN =		{urn:nbn:de:0030-drops-125082},
  doi =		{10.4230/LIPIcs.ICALP.2020.101},
  annote =	{Keywords: Multiway Cut, Kernelization, Small Set Expansion, Mimicking Networks}
}
  • Refine by Author
  • 19 Wahlström, Magnus
  • 4 Gutin, Gregory
  • 3 Eiben, Eduard
  • 3 Reidl, Felix
  • 2 Li, Shaohua
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 5 parameterized complexity
  • 3 Parameterized Algorithms
  • 2 Kernelization
  • 2 Parameterized complexity
  • 2 constraint satisfaction
  • Show More...

  • Refine by Type
  • 22 document
  • 1 volume

  • Refine by Publication Year
  • 5 2020
  • 4 2023
  • 3 2017
  • 2 2021
  • 2 2024
  • Show More...

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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact