Search Results

Documents authored by Rai, Ashutosh

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.50
On the Parameterized Complexity of Diverse SAT

Authors: Neeldhara Misra, Harshil Mittal, and Ashutosh Rai

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i.e., sufficiently dissimilar from each other) for a suitable notion of distance/dissimilarity between solutions. Interpreting assignments as bit vectors, we take their Hamming distance to quantify dissimilarity, and we focus on the problem of finding two solutions. Specifically, we define the problem Max Differ SAT (resp. Exact Differ SAT) as follows: Given a Boolean formula ϕ on n variables, decide whether ϕ has two satisfying assignments that differ on at least (resp. exactly) d variables. We study the classical and parameterized (in parameters d and n-d) complexities of Max Differ SAT and Exact Differ SAT, when restricted to some classes of formulas on which SAT is known to be polynomial-time solvable. In particular, we consider affine formulas, Krom formulas (i.e., 2-CNF formulas) and hitting formulas. For affine formulas, we show the following: Both problems are polynomial-time solvable when each equation has at most two variables. Exact Differ SAT is NP-hard, even when each equation has at most three variables and each variable appears in at most four equations. Also, Max Differ SAT is NP-hard, even when each equation has at most four variables. Both problems are 𝖶[1]-hard in the parameter n-d. In contrast, when parameterized by d, Exact Differ SAT is 𝖶[1]-hard, but Max Differ SAT admits a single-exponential FPT algorithm and a polynomial-kernel. For Krom formulas, we show the following: Both problems are polynomial-time solvable when each variable appears in at most two clauses. Also, both problems are 𝖶[1]-hard in the parameter d (and therefore, it turns out, also NP-hard), even on monotone inputs (i.e., formulas with no negative literals). Finally, for hitting formulas, we show that both problems can be solved in polynomial-time.
Cite as

Neeldhara Misra, Harshil Mittal, and Ashutosh Rai. On the Parameterized Complexity of Diverse SAT. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.ISAAC.2024.50,
  author =	{Misra, Neeldhara and Mittal, Harshil and Rai, Ashutosh},
  title =	{{On the Parameterized Complexity of Diverse SAT}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.50},
  URN =		{urn:nbn:de:0030-drops-221773},
  doi =		{10.4230/LIPIcs.ISAAC.2024.50},
  annote =	{Keywords: Diverse solutions, Affine formulas, 2-CNF formulas, Hitting formulas}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.56
Parameterized Approximation Scheme for Feedback Vertex Set

Authors: Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time 𝒪^*(3.460^k) and 𝒪^*(2.7^k) respectively. In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times 𝒪^*(2^{εk}⋅ 2.7^{(1-ε)k}), 𝒪^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and 𝒪^*(4^{(1-ε)k}) respectively for every ε ∈ (0,1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS.
Cite as

Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh. Parameterized Approximation Scheme for Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jana_et_al:LIPIcs.MFCS.2023.56,
  author =	{Jana, Satyabrata and Lokshtanov, Daniel and Mandal, Soumen and Rai, Ashutosh and Saurabh, Saket},
  title =	{{Parameterized Approximation Scheme for Feedback Vertex Set}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56},
  URN =		{urn:nbn:de:0030-drops-185902},
  doi =		{10.4230/LIPIcs.MFCS.2023.56},
  annote =	{Keywords: Feedback Vertex Set, Parameterized Approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.88
Parameterized Complexity of Untangling Knots

Authors: Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer

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

Abstract
Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II^- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.
Cite as

Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer. Parameterized Complexity of Untangling Knots. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{legrandduchesne_et_al:LIPIcs.ICALP.2022.88,
  author =	{Legrand-Duchesne, Cl\'{e}ment and Rai, Ashutosh and Tancer, Martin},
  title =	{{Parameterized Complexity of Untangling Knots}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{88:1--88:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.88},
  URN =		{urn:nbn:de:0030-drops-164296},
  doi =		{10.4230/LIPIcs.ICALP.2022.88},
  annote =	{Keywords: unknot recognition, parameterized complexity, Reidemeister moves, W\lbrackP\rbrack-complete}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.18
On Extended Formulations For Parameterized Steiner Trees

Authors: Andreas Emil Feldmann and Ashutosh Rai

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

Abstract
We present a novel linear program (LP) for the Steiner Tree problem, where a set of terminal vertices needs to be connected by a minimum weight tree in a graph G = (V,E) with non-negative edge weights. This well-studied problem is NP-hard and therefore does not have a compact extended formulation (describing the convex hull of all Steiner trees) of polynomial size, unless P=NP. On the other hand, Steiner Tree is fixed-parameter tractable (FPT) when parameterized by the number k of terminals, and can be solved in O(3^k|V|+2^k|V|²) time via the Dreyfus-Wagner algorithm. A natural question thus is whether the Steiner Tree problem admits an extended formulation of comparable size. We first answer this in the negative by proving a lower bound on the extension complexity of the Steiner Tree polytope, which, for some constant c > 0, implies that no extended formulation of size f(k)2^{cn} exists for any function f. However, we are able to circumvent this lower bound due to the fact that the edge weights are non-negative: we prove that Steiner Tree admits an integral LP with O(3^k|E|) variables and constraints. The size of our LP matches the runtime of the Dreyfus-Wagner algorithm, and our poof gives a polyhedral perspective on this classic algorithm. Our proof is simple, and additionally improves on a previous result by Siebert et al. [2018], who gave an integral LP of size O((2k/e)^k)|V|^{O(1)}.
Cite as

Andreas Emil Feldmann and Ashutosh Rai. On Extended Formulations For Parameterized Steiner Trees. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.IPEC.2021.18,
  author =	{Feldmann, Andreas Emil and Rai, Ashutosh},
  title =	{{On Extended Formulations For Parameterized Steiner Trees}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{18:1--18:16},
  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.18},
  URN =		{urn:nbn:de:0030-drops-154010},
  doi =		{10.4230/LIPIcs.IPEC.2021.18},
  annote =	{Keywords: Steiner trees, integral linear program, extension complexity, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.17
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem

Authors: Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai

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

Abstract
We develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with n vertices and integer edge weights is given together with an integer k, and the aim is to find k cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into k cliques. It was shown that ECP admits a kernel with k² vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of 2^𝒪(k²)n^O(1) [Issac, 2019]. For WECP we develop a compression (to a slightly more general problem) with 4^k vertices, and an algorithm with runtime 2^𝒪(k^(3/2)w^(1/2)log(k/w))n^O(1), where w is the maximum edge weight. The latter in particular improves the runtime for ECP to 2^𝒪(k^(3/2)log k)n^O(1).
Cite as

Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai. Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.IPEC.2020.17,
  author =	{Feldmann, Andreas Emil and Issac, Davis and Rai, Ashutosh},
  title =	{{Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-133206},
  doi =		{10.4230/LIPIcs.IPEC.2020.17},
  annote =	{Keywords: Edge Clique Partition, fixed-parameter tractability, kernelization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.70
Quick Separation in Chordal and Split Graphs

Authors: Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma

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

Abstract
In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (s_i, t_i), i ∈ [𝓁], and a positive integer k and the goal is to decide if there exists a vertex subset S ⊆ V(G)⧵ {s_i,t_i : i ∈ [𝓁]} of size at most k such that for every vertex pair (s_i,t_i), s_i and t_i are in two different connected components of G-S. In Unrestricted Multicut, the solution S can possibly pick the vertices in the vertex pairs {(s_i,t_i): i ∈ [𝓁]}. An important special case of the Multicut problem is the Multiway Cut problem, where instead of vertex pairs, we are given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T× T. The fixed parameter tractability (FPT) of these problems was a long-standing open problem and has been resolved fairly recently. Multicut and Multiway Cut now admit algorithms with running times 2^{{𝒪}(k³)}n^{{𝒪}(1)} and 2^k n^{{𝒪}(1)}, respectively. However, the kernelization complexity of both these problems is not fully resolved: while Multicut cannot admit a polynomial kernel under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for Multiway Cut. Towards designing faster FPT algorithms and polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results. 1) Multicut on chordal graphs admits a polynomial kernel with {𝒪}(k³ 𝓁⁷) vertices. Multiway Cut on chordal graphs admits a polynomial kernel with {𝒪}(k^{13}) vertices. 2) Multicut on chordal graphs can be solved in time min {𝒪(2^{k} ⋅ (k³+𝓁) ⋅ (n+m)), 2^{𝒪(𝓁 log k)} ⋅ (n+m) + 𝓁 (n+m)}. Hence Multicut on chordal graphs parameterized by the number of terminals is in XP. 3) Multicut on split graphs can be solved in time min {𝒪(1.2738^k + kn+𝓁(n+m), 𝒪(2^{𝓁} ⋅ 𝓁 ⋅ (n+m))}. Unrestricted Multicut on split graphs can be solved in time 𝒪(4^{𝓁}⋅ 𝓁 ⋅ (n+m)).
Cite as

Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma. Quick Separation in Chordal and Split Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.MFCS.2020.70,
  author =	{Misra, Pranabendu and Panolan, Fahad and Rai, Ashutosh and Saurabh, Saket and Sharma, Roohani},
  title =	{{Quick Separation in Chordal and Split Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{70:1--70: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.70},
  URN =		{urn:nbn:de:0030-drops-127391},
  doi =		{10.4230/LIPIcs.MFCS.2020.70},
  annote =	{Keywords: chordal graphs, multicut, multiway cut, FPT, kernel}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.10
A Polynomial Kernel for Diamond-Free Editing

Authors: Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Given a fixed graph H, the H-free editing problem asks whether we can edit at most k edges to make a graph contain no induced copy of H. We obtain a polynomial kernel for this problem when H is a diamond. The incompressibility dichotomy for H being a 3-connected graph and the classical complexity dichotomy suggest that except for H being a complete/empty graph, H-free editing problems admit polynomial kernels only for a few small graphs H. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.
Cite as

Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye. A Polynomial Kernel for Diamond-Free Editing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ESA.2018.10,
  author =	{Cao, Yixin and Rai, Ashutosh and Sandeep, R. B. and Ye, Junjie},
  title =	{{A Polynomial Kernel for Diamond-Free Editing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.10},
  URN =		{urn:nbn:de:0030-drops-94732},
  doi =		{10.4230/LIPIcs.ESA.2018.10},
  annote =	{Keywords: Kernelization, Diamond-free, H-free editing, Graph modification problem}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.21
Strong Parameterized Deletion: Bipartite Graphs

Authors: Ashutosh Rai and M. S. Ramanujan

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
The purpose of this article is two fold: (a) to formally introduce a stronger version of graph deletion problems; and (b) to study this version in the context of bipartite graphs. Given a family of graphs F, a typical instance of parameterized graph deletion problem consists of an undirected graph G and a positive integer k and the objective is to check whether we can delete at most k vertices (or k edges) such that the resulting graph belongs to F. Another version that has been recently studied is the one where the input contains two integers k and l and the objective is to check whether we can delete at most k vertices and l edges such that the resulting graph belongs to F. In this paper, we propose and initiate the study of a more general version which we call strong deletion. In this problem, given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be transformed into a graph in F by deleting at most l edges. In this paper we study this stronger version of deletion problems for the class of bipartite graphs. In particular, we study Strong Bipartite Deletion, where given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be made bipartite by deleting at most l edges. While fixed-parameter tractability when parameterizing by k or l alone is unlikely, we show that this problem is fixed-parameter tractable (FPT) when parameterized by both k and l.
Cite as

Ashutosh Rai and M. S. Ramanujan. Strong Parameterized Deletion: Bipartite Graphs. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rai_et_al:LIPIcs.FSTTCS.2016.21,
  author =	{Rai, Ashutosh and Ramanujan, M. S.},
  title =	{{Strong Parameterized Deletion: Bipartite Graphs}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.21},
  URN =		{urn:nbn:de:0030-drops-68561},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.21},
  annote =	{Keywords: fixed parameter tractable, bipartite-editing, recursive understanding}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.23
Lossy Kernels for Graph Contraction Problems

Authors: R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We study some well-known graph contraction problems in the recently introduced framework of lossy kernelization. In classical kernelization, given an instance (I,k) of a parameterized problem, we are interested in obtaining (in polynomial time) an equivalent instance (I',k') of the same problem whose size is bounded by a function in k. This notion however has a major limitation. Given an approximate solution to the instance (I',k'), we can say nothing about the original instance (I,k). To handle this issue, among others, the framework of lossy kernelization was introduced. In this framework, for a constant alpha, given an instance (I,k) we obtain an instance (I',k') of the same problem such that, for every c>1, any c-approximate solution to (I',k') can be turned into a (c*alpha)-approximate solution to the original instance (I, k) in polynomial time. Naturally, we are interested in a polynomial time algorithm for this task, and further require that |I'| + k' = k^{O(1)}. Akin to the notion of polynomial time approximation schemes in approximation algorithms, a parameterized problem is said to admit a polynomial size approximate kernelization scheme (PSAKS) if it admits a polynomial size alpha-approximate kernel for every approximation parameter alpha > 1. In this work, we design PSAKSs for Tree Contraction, Star Contraction, Out-Tree Contraction and Cactus Contraction problems. These problems do not admit polynomial kernels, and we show that each of them admit a PSAKS with running time k^{f(alpha)}|I|^{O(1)} that returns an instance of size k^{g(alpha)} where f(alpha) and g(alpha) are constants depending on alpha.
Cite as

R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale. Lossy Kernels for Graph Contraction Problems. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{krithika_et_al:LIPIcs.FSTTCS.2016.23,
  author =	{Krithika, R. and Misra, Pranabendu and Rai, Ashutosh and Tale, Prafullkumar},
  title =	{{Lossy Kernels for Graph Contraction Problems}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.23},
  URN =		{urn:nbn:de:0030-drops-68587},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.23},
  annote =	{Keywords: parameterized complexity, lossy kernelization, graph theory, edge contraction problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.43
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound

Authors: Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N. Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.
Cite as

Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2013.43,
  author =	{Crowston, Robert and Jones, Mark and Muciaccia, Gabriele and Philip, Geevarghese and Rai, Ashutosh and Saurabh, Saket},
  title =	{{Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{43--54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.43},
  URN =		{urn:nbn:de:0030-drops-43599},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.43},
  annote =	{Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut}
}
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 About DROPS Imprint Privacy Contact