78 Search Results for "Pilipczuk, Marcin"

Volume

LIPIcs, Volume 180

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference)

Editors: Yixin Cao and Marcin Pilipczuk

Document
DOI: 10.4230/LIPIcs.STACS.2024.4
Max Weight Independent Set in Sparse Graphs with No Long Claws

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.
Cite as

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski. Max Weight Independent Set in Sparse Graphs with No Long Claws. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrishami_et_al:LIPIcs.STACS.2024.4,
  author =	{Abrishami, Tara and Chudnovsky, Maria and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Max Weight Independent Set in Sparse Graphs with No Long Claws}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.4},
  URN =		{urn:nbn:de:0030-drops-197148},
  doi =		{10.4230/LIPIcs.STACS.2024.4},
  annote =	{Keywords: Max Weight Independent Set, subdivided claw, hereditary classes}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.11
Parameterized Complexity Classification for Interval Constraints

Authors: Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma

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

Abstract
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most k constraints, where k is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen’s interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set A of 13 basic comparison relations such as "precedes" or "during" for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP(Γ) for all Γ ⊆ A. IA is sometimes extended with unions of the relations in A or first-order definable relations over A, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP(A) in general, we then consider (parameterized) approximation algorithms. We first show that MinCSP(A) cannot be polynomial-time approximated within any constant factor and continue by presenting a factor-2 fpt-approximation algorithm. Once again, this algorithm has its roots in flow augmentation.
Cite as

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma. Parameterized Complexity Classification for Interval Constraints. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.IPEC.2023.11,
  author =	{Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Pilipczuk, Marcin and Sharma, Roohani},
  title =	{{Parameterized Complexity Classification for Interval Constraints}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-194306},
  doi =		{10.4230/LIPIcs.IPEC.2023.11},
  annote =	{Keywords: (minimum) constraint satisfaction problem, Allen’s interval algebra, parameterized complexity, cut problems}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.6
On the Complexity of Problems on Tree-Structured Graphs

Authors: Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk

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

Abstract
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)n^O(1) time and f(k)log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on "tree-structured graphs" are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a "natural home" for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)n^O(1) and use f(k)log n space. Moreover, we introduce "tree-shaped" variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.
Cite as

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.6,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Pilipczuk, Marcin and Pilipczuk, Micha{\l}},
  title =	{{On the Complexity of Problems on Tree-Structured Graphs}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{6:1--6: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.6},
  URN =		{urn:nbn:de:0030-drops-173626},
  doi =		{10.4230/LIPIcs.IPEC.2022.6},
  annote =	{Keywords: Parameterized Complexity, Treewidth, XALP, XNLP}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.24
List Colouring Trees in Logarithmic Space

Authors: Hans L. Bodlaender, Carla Groenland, and Hugo Jacob

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1,… ,n} of available colours for each v ∈ V, a list colouring for G is a proper colouring c such that c(v) ∈ L(v) for all v.
Cite as

Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List Colouring Trees in Logarithmic Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.ESA.2022.24,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo},
  title =	{{List Colouring Trees in Logarithmic Space}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.24},
  URN =		{urn:nbn:de:0030-drops-169620},
  doi =		{10.4230/LIPIcs.ESA.2022.24},
  annote =	{Keywords: List colouring, trees, space complexity, logspace, graph algorithms, tree-partition-width}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.58
Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
Cite as

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ESA.2022.58,
  author =	{Gajarsk\'{y}, Jakub and Jaffke, Lars and Lima, Paloma T. and Novotn\'{a}, Jana and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Souza, U\'{e}verton S.},
  title =	{{Taming Graphs with No Large Creatures and Skinny Ladders}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.58},
  URN =		{urn:nbn:de:0030-drops-169969},
  doi =		{10.4230/LIPIcs.ESA.2022.58},
  annote =	{Keywords: Minimal separator, hereditary graph class}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.79
Computing Treedepth in Polynomial Space and Linear FPT Time

Authors: Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
The treedepth of a graph G is the least possible depth of an elimination forest of G: a rooted forest on the same vertex set where every pair of vertices adjacent in G is bound by the ancestor/descendant relation. We propose an algorithm that given a graph G and an integer d, either finds an elimination forest of G of depth at most d or concludes that no such forest exists; thus the algorithm decides whether the treedepth of G is at most d. The running time is 2^𝒪(d²)⋅n^𝒪(1) and the space usage is polynomial in n. Further, by allowing randomization, the time and space complexities can be improved to 2^𝒪(d²)⋅n and d^𝒪(1)⋅n, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity 2^𝒪(d²)⋅n, but uses exponential space.
Cite as

Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing Treedepth in Polynomial Space and Linear FPT Time. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nadara_et_al:LIPIcs.ESA.2022.79,
  author =	{Nadara, Wojciech and Pilipczuk, Micha{\l} and Smulewicz, Marcin},
  title =	{{Computing Treedepth in Polynomial Space and Linear FPT Time}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.79},
  URN =		{urn:nbn:de:0030-drops-170175},
  doi =		{10.4230/LIPIcs.ESA.2022.79},
  annote =	{Keywords: treedepth, FPT, polynomial space}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.93
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument

Authors: Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw S_{t,t,t} as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2^𝒪(√nlog n) and a quasipolynomial-time approximation scheme with improved running time 2^𝒪(ε^{-1} log⁵ n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in P_t-free graphs, ensures that given an n-vertex P_t-free graph, in polynomial time we can find a set P of at most t-1 vertices, such that every connected component of G-N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, in polynomial time we can find a set P of 𝒪(t log n) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G-N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices.
Cite as

Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{majewski_et_al:LIPIcs.ICALP.2022.93,
  author =	{Majewski, Konrad and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Soko{\l}owski, Marek},
  title =	{{Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gy\'{a}rf\'{a}s' Path Argument}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93},
  URN =		{urn:nbn:de:0030-drops-164343},
  doi =		{10.4230/LIPIcs.ICALP.2022.93},
  annote =	{Keywords: Max Independent Set, subdivided claw, QPTAS, subexponential-time algorithm}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.21
Close Relatives (Of Feedback Vertex Set), Revisited

Authors: Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk

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

Abstract
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{𝒪(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{𝒪(1)} ⋅ n-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work. - Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time 2^{𝒪(k log k)} ⋅ n in graphs of treewidth at most k. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al. and improves the polynomial factor in some of their upper bounds. - Subset Feedback Vertex Set and Node Multiway Cut can be solved in time 2^{𝒪(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k. - Odd Cycle Transversal can be solved in time 4^k ⋅ k^{𝒪(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{𝒪(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with 𝒪(k) nodes. This results in a 2^{𝒪(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{𝒪(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.
Cite as

Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2021.21,
  author =	{Jacob, Hugo and Bellitto, Thomas and Defrain, Oscar and Pilipczuk, Marcin},
  title =	{{Close Relatives (Of Feedback Vertex Set), Revisited}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{21:1--21:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.21},
  URN =		{urn:nbn:de:0030-drops-154049},
  doi =		{10.4230/LIPIcs.IPEC.2021.21},
  annote =	{Keywords: feedback vertex set, treewidth, cliquewidth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.24
Hardness of Metric Dimension in Graphs of Constant Treewidth

Authors: Shaohua Li and Marcin Pilipczuk

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

Abstract
The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S ⊆ V(G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24.
Cite as

Shaohua Li and Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.IPEC.2021.24,
  author =	{Li, Shaohua and Pilipczuk, Marcin},
  title =	{{Hardness of Metric Dimension in Graphs of Constant Treewidth}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{24:1--24:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.24},
  URN =		{urn:nbn:de:0030-drops-154071},
  doi =		{10.4230/LIPIcs.IPEC.2021.24},
  annote =	{Keywords: Graph algorithms, parameterized complexity, width parameters, NP-hard}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.49
Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings

Authors: Shaohua Li, Marcin Pilipczuk, and Manuel Sorge

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Given a graph G = (V,E) and an integer k, the Cluster Editing problem asks whether we can transform G into a union of vertex-disjoint cliques by at most k modifications (edge deletions or insertions). In this paper, we study the following variant of Cluster Editing. We are given a graph G = (V,E), a packing ℋ of modification-disjoint induced P₃s (no pair of P₃s in H share an edge or non-edge) and an integer 𝓁. The task is to decide whether G can be transformed into a union of vertex-disjoint cliques by at most 𝓁+|H| modifications (edge deletions or insertions). We show that this problem is NP-hard even when 𝓁 = 0 (in which case the problem asks to turn G into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of H) and when each vertex is in at most 23 P₃s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer c such that the problem remains tractable when restricting to packings such that each vertex is in at most c packed P₃s. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect to 𝓁 and we show that the case c = 2 is solvable in |V|^{2𝓁 + O(1)} time.
Cite as

Shaohua Li, Marcin Pilipczuk, and Manuel Sorge. Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2021.49,
  author =	{Li, Shaohua and Pilipczuk, Marcin and Sorge, Manuel},
  title =	{{Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus 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.2021.49},
  URN =		{urn:nbn:de:0030-drops-136945},
  doi =		{10.4230/LIPIcs.STACS.2021.49},
  annote =	{Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.IPEC.2020
LIPIcs, Volume 180, IPEC 2020, Complete Volume

Authors: Yixin Cao and Marcin Pilipczuk

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

Abstract
LIPIcs, Volume 180, IPEC 2020, Complete Volume
Cite as

15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 1-498, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.IPEC.2020,
  title =	{{LIPIcs, Volume 180, IPEC 2020, Complete Volume}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{1--498},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020},
  URN =		{urn:nbn:de:0030-drops-133022},
  doi =		{10.4230/LIPIcs.IPEC.2020},
  annote =	{Keywords: LIPIcs, Volume 180, IPEC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.IPEC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yixin Cao and Marcin Pilipczuk

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

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

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

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.IPEC.2020.0,
  author =	{Cao, Yixin and Pilipczuk, Marcin},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{0:i--0:xviii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.0},
  URN =		{urn:nbn:de:0030-drops-133035},
  doi =		{10.4230/LIPIcs.IPEC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.1
On the Parameterized Complexity of Clique Elimination Distance

Authors: Akanksha Agrawal and M. S. Ramanujan

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

Abstract
Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance in an effort to define new tractable parameterizations for graph problems and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. In this paper, we consider the problem of computing the elimination distance of a given graph to the class of cluster graphs and initiate the study of the parameterized complexity of a more general version - that of obtaining a modulator to such graphs. That is, we study the (η,Clq)-Elimination Deletion problem ((η,Clq)-ED Deletion) where, for a fixed η, one is given a graph G and k ∈ ℕ and the objective is to determine whether there is a set S ⊆ V(G) such that the graph G-S has elimination distance at most η to the class of cluster graphs. Our main result is a polynomial kernelization (parameterized by k) for this problem. As components in the proof of our main result, we develop a k^𝒪(η k + η²)n^𝒪(1)-time fixed-parameter algorithm for (η,Clq)-ED Deletion and a polynomial-time factor-min{𝒪(η⋅ opt⋅ log² n),opt^𝒪(1)} approximation algorithm for the same problem.
Cite as

Akanksha Agrawal and M. S. Ramanujan. On the Parameterized Complexity of Clique Elimination Distance. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2020.1,
  author =	{Agrawal, Akanksha and Ramanujan, M. S.},
  title =	{{On the Parameterized Complexity of Clique Elimination Distance}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{1:1--1:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.1},
  URN =		{urn:nbn:de:0030-drops-133043},
  doi =		{10.4230/LIPIcs.IPEC.2020.1},
  annote =	{Keywords: Elimination Distance, Cluster Graphs, Kernelization}
}
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-dev.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}
}
  • Refine by Author
  • 31 Pilipczuk, Marcin
  • 9 Pilipczuk, Michal
  • 8 Wrochna, Marcin
  • 5 Li, Shaohua
  • 5 Nadara, Wojciech
  • Show More...

  • Refine by Classification
  • 25 Theory of computation → Parameterized complexity and exact algorithms
  • 24 Theory of computation → Graph algorithms analysis
  • 15 Mathematics of computing → Graph algorithms
  • 15 Theory of computation → Fixed parameter tractability
  • 4 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 10 parameterized complexity
  • 8 fixed-parameter tractability
  • 6 treedepth
  • 4 Kernelization
  • 4 Treedepth
  • Show More...

  • Refine by Type
  • 77 document
  • 1 volume

  • Refine by Publication Year
  • 42 2020
  • 7 2019
  • 6 2018
  • 5 2016
  • 5 2017
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact