Search Results

Documents authored by Jain, Pallavi

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.88
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

Authors: Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana

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

Abstract
In the MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. Maximum Coverage can be seen as a special case of CC-MaxSat, where the formula Φ is monotone, i.e., does not contain any negative literals. CC-MaxSat and Maximum Coverage are extremely well-studied problems in the approximation algorithms as well as the parameterized complexity literature. Our first conceptual contribution is that CC-MaxSat and Maximum Coverage are equivalent to each other in the context of FPT-Approximation parameterized by k (here, the approximation is in terms of the number of clauses satisfied/elements covered). In particular, we give a randomized reduction from CC-MaxSat to Maximum Coverage running in time 𝒪(1/ε)^{k} ⋅ (m+n)^{𝒪(1)} that preserves the approximation guarantee up to a factor of (1-ε). Furthermore, this reduction also works in the presence of "fairness" constraints on the satisfied clauses, as well as matroid constraints on the set of variables that are assigned true. Here, the "fairness" constraints are modeled by partitioning the clauses of the formula Φ into r different colors, and the goal is to find an assignment that satisfies at least t_j clauses of each color 1 ≤ j ≤ r. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for Maximum Coverage and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSat and Maximum Coverage for K_{d,d}-free set systems (i.e., no d sets share d elements), as well as a recent FPT-AS for Matroid Constrained Maximum Coverage by Sellier [ESA 2023] for frequency-d set systems.
Cite as

Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88,
  author =	{Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya},
  title =	{{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{88:1--88: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.88},
  URN =		{urn:nbn:de:0030-drops-202318},
  doi =		{10.4230/LIPIcs.ICALP.2024.88},
  annote =	{Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.24
On the (Parameterized) Complexity of Almost Stable Marriage

Authors: Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
In the Stable Marriage problem, when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the "no blocking pair" condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, the goal is to find a matching whose size exceeds that of a stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is "closest", in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.
Cite as

Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. On the (Parameterized) Complexity of Almost Stable Marriage. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2020.24,
  author =	{Gupta, Sushmita and Jain, Pallavi and Roy, Sanjukta and Saurabh, Saket and Zehavi, Meirav},
  title =	{{On the (Parameterized) Complexity of Almost Stable Marriage}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.24},
  URN =		{urn:nbn:de:0030-drops-132655},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.24},
  annote =	{Keywords: Stable Matching, Parameterized Complexity, Local Search}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.51
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Authors: Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
A graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the F-Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k, F-Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and |X| ≤ k. Here, G/X is the graph obtained from G by contracting edges in X. We obtain the following results for the F-Contraction problem. - Clique Contraction is known to be FPT. However, unless NP ⊆ coNP/poly, it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme (PSAKS). That is, it admits a (1 + ε)-approximate kernel with {O}(k^{f(ε)}) vertices for every ε > 0. - Split Contraction is known to be W[1]-Hard. We deconstruct this intractability result in two ways. Firstly, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)-FPT-approximation algorithm for Split Contraction). Furthermore, we show that, assuming Gap-ETH, there is no (5/4-δ)-FPT-approximation algorithm for Split Contraction. Here, ε, δ > 0 are fixed constants. - Chordal Contraction is known to be W[2]-Hard. We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1], there is no F(k)-FPT-approximation algorithm for Chordal Contraction. Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k)-FPT-approximation algorithm for the F-Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and |X| ≤ k, it outputs an edge set Y of size at most h(k) ⋅ k for which G/Y is in F. We find it extremely interesting that three closely related problems have different behavior with respect to FPT-approximation.
Cite as

Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gunda_et_al:LIPIcs.APPROX/RANDOM.2020.51,
  author =	{Gunda, Spoorthy and Jain, Pallavi and Lokshtanov, Daniel and Saurabh, Saket and Tale, Prafullkumar},
  title =	{{On the Parameterized Approximability of Contraction to Classes of Chordal Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{51:1--51:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.51},
  URN =		{urn:nbn:de:0030-drops-126545},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.51},
  annote =	{Keywords: Graph Contraction, FPT-Approximation, Inapproximability, Lossy Kernels}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.18
Exact and Approximate Digraph Bandwidth

Authors: Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph D and an ordering sigma of its vertices, the digraph bandwidth of sigma with respect to D is equal to the maximum value of sigma(v)-sigma(u) over all arcs (u,v) of D going forward along sigma (that is, when sigma(u) < sigma (v)). The Digraph Bandwidth problem takes as input a digraph D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidth easily reduces to Digraph Bandwidth and thus, it immediately implies that Directed Bandwidth is {NP-hard}. While an O^*(n!) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form 2^O(n). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph D, respectively. - Digraph Bandwidth can be solved in O^*(3^n * 2^m) time. This result implies a 2^O(n) time algorithm on sparse graphs, such as graphs of bounded average degree. - Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most t, then Digraph Bandwidth can be solved in time O^*(2^(n + (t+2) log n)). This result implies a 2^(n+O(sqrt(n) log n)) algorithm for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph H as a minor. - Digraph Bandwidth can be solved in min{O^*(4^n * b^n), O^*(4^n * 2^(b log b log n))} time, where b denotes the optimal digraph bandwidth of D. This allow us to deduce a 2^O(n) algorithm in many cases, for example when b <= n/(log^2n). - Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real epsilon > 0, we can find an ordering whose digraph bandwidth is at most (1+epsilon) times the optimal digraph bandwidth, in time O^*(4^n * (ceil[4/epsilon])^n).
Cite as

Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh, and Roohani Sharma. Exact and Approximate Digraph Bandwidth. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.FSTTCS.2019.18,
  author =	{Jain, Pallavi and Kanesh, Lawqueen and Lochet, William and Saurabh, Saket and Sharma, Roohani},
  title =	{{Exact and Approximate Digraph Bandwidth}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.18},
  URN =		{urn:nbn:de:0030-drops-115802},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.18},
  annote =	{Keywords: directed bandwidth, digraph bandwidth, approximation scheme, exact exponential algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.35
Parameterized Complexity of Conflict-Free Matchings and Paths

Authors: Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) is a solution to I in Gamma, which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Matching (CF-Matching) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-Matching and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-Matching holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-Matching when the conflict graph is chordal. Also, we give FPT algorithms for both CF-Matching and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-Matching and CF-SP, where the conflicting conditions are given by a (representable) matroid.
Cite as

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2019.35,
  author =	{Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Saurabh, Saket},
  title =	{{Parameterized Complexity of Conflict-Free Matchings and Paths}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-109798},
  doi =		{10.4230/LIPIcs.MFCS.2019.35},
  annote =	{Keywords: Conflict-free, Matching, Shortest Path, FPT algorithm, W\lbrack1\rbrack-hard, Matroid}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.14
Exploring the Kernelization Borders for Hitting Cycles

Authors: Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
A generalization of classical cycle hitting problems, called conflict version of the problem, is defined as follows. An input is undirected graphs G and H on the same vertex set, and a positive integer k, and the objective is to decide whether there exists a vertex subset X subseteq V(G) such that it intersects all desired "cycles" (all cycles or all odd cycles or all even cycles) and X is an independent set in H. In this paper we study the conflict version of classical Feedback Vertex Set, and Odd Cycle Transversal problems, from the view point of kernelization complexity. In particular, we obtain the following results, when the conflict graph H belongs to the family of d-degenerate graphs. 1) CF-FVS admits a O(k^{O(d)}) kernel. 2) CF-OCT does not admit polynomial kernel (even when H is 1-degenerate), unless NP subseteq coNP/poly. For our kernelization algorithm we exploit ideas developed for designing polynomial kernels for the classical Feedback Vertex Set problem, as well as, devise new reduction rules that exploit degeneracy crucially. Our main conceptual contribution here is the notion of "k-independence preserver". Informally, it is a set of "important" vertices for a given subset X subseteq V(H), that is enough to capture the independent set property in H. We show that for d-degenerate graph independence preserver of size k^{O(d)} exists, and can be used in designing polynomial kernel.
Cite as

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh. Exploring the Kernelization Borders for Hitting Cycles. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2018.14,
  author =	{Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Misra, Pranabendu and Saurabh, Saket},
  title =	{{Exploring the Kernelization Borders for Hitting Cycles}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.14},
  URN =		{urn:nbn:de:0030-drops-102158},
  doi =		{10.4230/LIPIcs.IPEC.2018.14},
  annote =	{Keywords: Parameterized Complexity, Kernelization, Conflict-free problems, Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.53
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

Authors: Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i,j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.
Cite as

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh. Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2018.53,
  author =	{Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Lokshtanov, Daniel and Saurabh, Saket},
  title =	{{Conflict Free Feedback Vertex Set: A Parameterized Dichotomy}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.53},
  URN =		{urn:nbn:de:0030-drops-96355},
  doi =		{10.4230/LIPIcs.MFCS.2018.53},
  annote =	{Keywords: Conflict-free, Feedback Vertex Set, FPT algorithm, W\lbrack1\rbrack-hardness}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact