Search Results

Documents authored by Roy, Shivesh K.

Document
DOI: 10.4230/LIPIcs.IPEC.2023.28
On the Parameterized Complexity of Multiway Near-Separator

Authors: Bart M. P. Jansen and Shivesh K. Roy

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

Abstract
We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph G, integer k, and terminal set T ⊆ V(G), it asks whether there is a vertex set S ⊆ V(G) ⧵ T of size at most k such that in graph G-S, no pair of distinct terminals can be connected by two pairwise internally vertex-disjoint paths. Hence each terminal pair can be separated in G-S by removing at most one vertex. The problem is therefore a generalization of (Node) Multiway Cut, which asks for a vertex set for which each terminal is in a different component of G-S. We develop a fixed-parameter tractable algorithm for Multiway Near-Separator running in time 2^{𝒪(k log k)} ⋅ n^{𝒪(1)}. Our algorithm is based on a new pushing lemma for solutions with respect to important separators, along with two problem-specific ingredients. The first is a polynomial-time subroutine to reduce the number of terminals in the instance to a polynomial in the solution size k plus the size of a given suboptimal solution. The second is a polynomial-time algorithm that, given a graph G and terminal set T ⊆ V(G) along with a single vertex x ∈ V(G) that forms a multiway near-separator, computes a 14-approximation for the problem of finding a multiway near-separator not containing x.
Cite as

Bart M. P. Jansen and Shivesh K. Roy. On the Parameterized Complexity of Multiway Near-Separator. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.28,
  author =	{Jansen, Bart M. P. and Roy, Shivesh K.},
  title =	{{On the Parameterized Complexity of Multiway Near-Separator}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{28:1--28:18},
  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.28},
  URN =		{urn:nbn:de:0030-drops-194470},
  doi =		{10.4230/LIPIcs.IPEC.2023.28},
  annote =	{Keywords: fixed-parameter tractability, multiway cut, near-separator}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.29
Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs

Authors: Bart M. P. Jansen and Shivesh K. Roy

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

Abstract
We study the kernelization complexity of the Weighted H-Packing problem on sparse graphs. For a fixed connected graph H, in the Weighted H-Packing problem the input is a graph G, a vertex-weight function w : V(G) → ℕ, and positive integers k, t. The question is whether there exist k vertex-disjoint subgraphs H₁, …, H_k of G such that H_i is isomorphic to H for each i ∈ [k] and the total weight of these k ⋅ |V(H)| vertices is at least t. It is known that the (unweighted) H-Packing problem admits a kernel with 𝒪(k^{|V(H)|-1}) vertices on general graphs, and a linear kernel on planar graphs and graphs of bounded genus. In this work, we focus on case that H is a clique on h ≥ 3 vertices (which captures Triangle Packing) and present a linear-vertex kernel for Weighted K_h-Packing on graphs of bounded expansion, along with a kernel with 𝒪(k^{1+ε}) vertices on nowhere-dense graphs for all ε > 0. To obtain these results, we combine two powerful ingredients in a novel way: the Erdős-Rado Sunflower lemma and the theory of sparsity.
Cite as

Bart M. P. Jansen and Shivesh K. Roy. Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.29,
  author =	{Jansen, Bart M. P. and Roy, Shivesh K.},
  title =	{{Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{29:1--29:13},
  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.29},
  URN =		{urn:nbn:de:0030-drops-194488},
  doi =		{10.4230/LIPIcs.IPEC.2023.29},
  annote =	{Keywords: kernelization, weighted problems, graph packing, sunflower lemma, bounded expansion, nowhere dense}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.64
On the Hardness of Compressing Weights

Authors: Bart M. P. Jansen, Shivesh K. Roy, and Michał Włodarczyk

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted graph and the goal is to detect a clique of total weight equal to a prescribed value. We show that the weighted variant, parameterized by the number of vertices n, is significantly harder than the unweighted problem by presenting an 𝒪(n^{3 - ε}) lower bound on the size of the kernel, under the assumption that NP ̸ ⊆ coNP/poly. This lower bound is essentially tight: we show that we can reduce the problem to the case with weights bounded by 2^𝒪(n), which yields a randomized kernel of 𝒪(n³) bits. We generalize these results to the weighted d-Uniform Hyperclique problem, Subset Sum, and weighted variants of Boolean Constraint Satisfaction Problems (CSPs). We also study weighted minimization problems and show that weight compression is easier when we only want to {preserve the collection of} optimal solutions. Namely, we show that for node-weighted Vertex Cover on bipartite graphs it is possible to maintain the set of optimal solutions using integer weights from the range [1, n], but if we want to maintain the ordering of the weights of all inclusion-minimal solutions, then weights as large as 2^Ω(n) are necessary.
Cite as

Bart M. P. Jansen, Shivesh K. Roy, and Michał Włodarczyk. On the Hardness of Compressing Weights. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 64:1-64:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.MFCS.2021.64,
  author =	{Jansen, Bart M. P. and Roy, Shivesh K. and W{\l}odarczyk, Micha{\l}},
  title =	{{On the Hardness of Compressing Weights}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{64:1--64:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.64},
  URN =		{urn:nbn:de:0030-drops-145049},
  doi =		{10.4230/LIPIcs.MFCS.2021.64},
  annote =	{Keywords: kernelization, compression, edge-weighted clique, constraint satisfaction problems}
}
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