35 Search Results for "Panolan, Fahad"


Document
Decremental Sensitivity Oracles for Covering and Packing Minors

Authors: Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Peter Strulo

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


Abstract
In this paper, we present the first decremental fixed-parameter sensitivity oracles for a number of basic covering and packing problems on graphs. In particular, we obtain the first decremental sensitivity oracles for Vertex Planarization (delete k vertices to make the graph planar) and Cycle Packing (pack k vertex-disjoint cycles in the given graph). That is, we give a sensitivity oracle that preprocesses the given graph in time f(k,𝓁)n^{{O}(1)} such that, when given a set of 𝓁 edge deletions, the data structure decides in time f(k,𝓁) whether the updated graph is a positive instance of the problem. These results are obtained as a corollary of our central result, which is the first decremental sensitivity oracle for Topological Minor Deletion (cover all topological minors in the input graph that belong to a specified set, using k vertices). Though our methodology closely follows the literature, we are able to produce the first explicit bounds on the preprocessing and query times for several problems. We also initiate the study of fixed-parameter sensitivity oracles with so-called structural parameterizations and give sufficient conditions for the existence of fixed-parameter sensitivity oracles where the parameter is just the treewidth of the graph. In contrast, all existing literature on this topic and the aforementioned results in this paper assume a bound on the solution size (a weaker parameter than treewidth for many problems). As corollaries, we obtain decremental sensitivity oracles for well-studied problems such as Vertex Cover and Dominating Set when only the treewidth of the input graph is bounded. A feature of our methodology behind these results is that we are able to obtain query times independent of treewidth.

Cite as

Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Peter Strulo. Decremental Sensitivity Oracles for Covering and Packing Minors. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kanesh_et_al:LIPIcs.STACS.2024.44,
  author =	{Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Strulo, Peter},
  title =	{{Decremental Sensitivity Oracles for Covering and Packing Minors}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{44:1--44:19},
  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.44},
  URN =		{urn:nbn:de:0030-drops-197544},
  doi =		{10.4230/LIPIcs.STACS.2024.44},
  annote =	{Keywords: Sensitivity oracles, Data Structures, FPT algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Backdoor Sets on Nowhere Dense SAT

Authors: Daniel Lokshtanov, Fahad Panolan, and M. S. Ramanujan

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


Abstract
For a satisfiable CNF formula ϕ and an integer t, a weak backdoor set to treewidth-t is a set of variables such that there is an assignment to this set that reduces ϕ to a satisfiable formula that has an incidence graph of treewidth at most t. A natural research program in the work on fixed-parameter algorithms (FPT algorithms) for SAT is to delineate the tractability borders for the problem of detecting a small weak backdoor set to treewidth-t formulas. In this line of research, Gaspers and Szeider (ICALP 2012) showed that detecting a weak backdoor set of size at most k to treewidth-1 is W[2]-hard parameterized by k if the input is an arbitrary CNF formula. Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015), showed that if the input is d-CNF, then detecting a weak backdoor set of size at most k to treewidth-t is fixed-parameter tractable (parameterized by k,t,d). These two results indicate that sparsity of the input plays a role in determining the parameterized complexity of detecting weak backdoor sets to treewidth-t. In this work, we take a major step towards characterizing the precise impact of sparsity on the parameterized complexity of this problem by obtaining algorithmic results for detecting small weak backdoor sets to treewidth-t for input formulas whose incidence graphs belong to a nowhere-dense graph class. Nowhere density provides a robust and well-understood notion of sparsity that is at the heart of several advances on model checking and structural graph theory. Moreover, nowhere-dense graph classes contain many well-studied graph classes such as bounded treewidth graphs, graphs that exclude a fixed (topological) minor and graphs of bounded expansion. Our main contribution is an algorithm that, given a formula ϕ whose incidence graph belongs to a fixed nowhere-dense graph class and an integer k, in time f(t,k)|ϕ|^O(1), either finds a satisfying assignment of ϕ, or concludes correctly that ϕ has no weak backdoor set of size at most k to treewidth-t. To obtain this algorithm, we develop a strategy that only relies on the fact that nowhere-dense graph classes are biclique-free. That is, for every nowhere-dense graph class, there is a p such that it is contained in the class of graphs that exclude K_{p,p} as a subgraph. This is a significant feature of our techniques since the class of biclique-free graphs also generalizes the class of graphs of bounded degeneracy, which are incomparable with nowhere-dense graph classes. As a result, our algorithm also generalizes the results of Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015) for the special case of d-CNF formulas as input when d is fixed. This is because the incidence graphs of such formulas exclude K_{d+1,d+1} as a subgraph.

Cite as

Daniel Lokshtanov, Fahad Panolan, and M. S. Ramanujan. Backdoor Sets on Nowhere Dense SAT. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2022.91,
  author =	{Lokshtanov, Daniel and Panolan, Fahad and Ramanujan, M. S.},
  title =	{{Backdoor Sets on Nowhere Dense SAT}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{91:1--91:20},
  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.91},
  URN =		{urn:nbn:de:0030-drops-164323},
  doi =		{10.4230/LIPIcs.ICALP.2022.91},
  annote =	{Keywords: Fixed-parameter Tractability, Satisfiability, Backdoors, Treewidth}
}
Document
An FPT Algorithm for Elimination Distance to Bounded Degree Graphs

Authors: Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh

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


Abstract
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance 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]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K₅-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

Cite as

Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. An FPT Algorithm for Elimination Distance to Bounded Degree Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2021.5,
  author =	{Agrawal, Akanksha and Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{An FPT Algorithm for Elimination Distance to Bounded Degree Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{5:1--5:11},
  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.5},
  URN =		{urn:nbn:de:0030-drops-136507},
  doi =		{10.4230/LIPIcs.STACS.2021.5},
  annote =	{Keywords: Elimination Distance, Fixed-parameter Tractability, Graph Modification}
}
Document
Diverse Collections in Matroids and Graphs

Authors: Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh

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


Abstract
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω:E(M)→N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k bases B_1, ..., B_k of M such that the weight of the symmetric difference of any pair of these bases is at least d. This is a diverse variant of the classical matroid base packing problem. The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M₁,M₂ defined on the same ground set E, a weight function ω:E→N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k common independent sets I_1, ..., I_k of M₁ and M₂ such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1, d ≥ 0. The task is to decide if G contains k perfect matchings M_1, ..., M_k such that the symmetric difference of any two of these matchings is at least d. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and Diverse Perfect Matchings is known to be NP-hard for k = 2. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard. We show also that Diverse Perfect Matchings cannot be solved in polynomial time (unless P=NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k,d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For Weighted Diverse Bases we present a polynomial-time algorithm that takes a representation of the input matroid over a finite field and computes a poly(k,d)-sized kernel for the problem.

Cite as

Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse Collections in Matroids and Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.STACS.2021.31,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket},
  title =	{{Diverse Collections in Matroids and Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{31:1--31:14},
  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.31},
  URN =		{urn:nbn:de:0030-drops-136769},
  doi =		{10.4230/LIPIcs.STACS.2021.31},
  annote =	{Keywords: Matroids, Diverse solutions, Fixed-parameter tractable algorithms}
}
Document
Structural Parameterizations with Modulator Oblivion

Authors: Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot

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


Abstract
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph, when parameterized by k. While this investigation fits naturally into the recent trend of what are called "structural parameterizations", here we assume that the deletion set is not given. One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k^O(k)n^O(1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph. In this work, we design 2^O(k)n^O(1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time 2^O(k)n^O(1) where each bag is a union of four cliques and O(k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).

Cite as

Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Structural Parameterizations with Modulator Oblivion. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2020.19,
  author =	{Jacob, Ashwin and Panolan, Fahad and Raman, Venkatesh and Sahlot, Vibha},
  title =	{{Structural Parameterizations with Modulator Oblivion}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{19:1--19:18},
  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.19},
  URN =		{urn:nbn:de:0030-drops-133222},
  doi =		{10.4230/LIPIcs.IPEC.2020.19},
  annote =	{Keywords: Parameterized Complexity, Chordal Graph, Tree Decomposition, Strong Exponential Time Hypothesis}
}
Document
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

Authors: Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz

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


Abstract
In a reconfiguration version of a decision problem 𝒬 the input is an instance of 𝒬 and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K_{d,d} as a subgraph, for some constant d ≥ 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k+𝓁, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.

Cite as

Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.IPEC.2020.24,
  author =	{Lokshtanov, Daniel and Mouawad, Amer E. and Panolan, Fahad and Siebertz, Sebastian},
  title =	{{On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{24:1--24:15},
  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.24},
  URN =		{urn:nbn:de:0030-drops-133276},
  doi =		{10.4230/LIPIcs.IPEC.2020.24},
  annote =	{Keywords: reconfiguration, parameterized complexity, connected dominating set, graph structure theory}
}
Document
Improved FPT Algorithms for Deletion to Forest-Like Structures

Authors: Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)


Abstract
The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V(G) of size at most k such that G-S is a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed a randomized algorithm for the problem running in time 𝒪^⋆(2.7^k). In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G-S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k,𝓁 ∈ ℕ, and the objective is to test whether there exists a vertex subset S of size at most k, such that G-S is 𝓁 edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algorithms for all these problems. In particular we obtain following randomized algorithms. 1) Independent Feedback Vertex Set can be solved in time 𝒪^⋆(2.7^k). 2) Pseudo Forest Deletion can be solved in time 𝒪^⋆(2.85^k). 3) Almost Forest Deletion can be solved in 𝒪^⋆(min{2.85^k ⋅ 8.54^𝓁, 2.7^k ⋅ 36.61^𝓁, 3^k ⋅ 1.78^𝓁}).

Cite as

Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh. Improved FPT Algorithms for Deletion to Forest-Like Structures. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gowda_et_al:LIPIcs.ISAAC.2020.34,
  author =	{Gowda, Kishen N. and Lonkar, Aditya and Panolan, Fahad and Patel, Vraj and Saurabh, Saket},
  title =	{{Improved FPT Algorithms for Deletion to Forest-Like Structures}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.34},
  URN =		{urn:nbn:de:0030-drops-133781},
  doi =		{10.4230/LIPIcs.ISAAC.2020.34},
  annote =	{Keywords: Parameterized Complexity, Independent Feedback Vertex Set, PseudoForest, Almost Forest, Cut and Count, Treewidth}
}
Document
Parameterized Complexity of Feedback Vertex Sets on Hypergraphs

Authors: Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

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


Abstract
A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows - HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). - If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{𝒪(k³log k)}n^{𝒪(1)}. - If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{𝒪(k)}n^{𝒪(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].

Cite as

Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized Complexity of Feedback Vertex Sets on Hypergraphs. 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. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.FSTTCS.2020.18,
  author =	{Choudhary, Pratibha and Kanesh, Lawqueen and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
  title =	{{Parameterized Complexity of Feedback Vertex Sets on Hypergraphs}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{18:1--18:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.18},
  URN =		{urn:nbn:de:0030-drops-132596},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.18},
  annote =	{Keywords: feedback vertex sets, hypergraphs, FPT, randomized algorithms}
}
Document
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-dev.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
APPROX
Low-Rank Binary Matrix Approximation in Column-Sum Norm

Authors: Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, and Kirill Simonov

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


Abstract
We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show that for every ε ∈ (0, 1), there is a {randomized} (1+ε)-approximation algorithm for 𝓁₁-Rank-r Approximation over {GF}(2) of running time m^{O(1)}n^{O(2^{4r}⋅ ε^{-4})}. This is the first polynomial time approximation scheme (PTAS) for this problem.

Cite as

Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, and Kirill Simonov. Low-Rank Binary Matrix Approximation in Column-Sum Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2020.32,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad and Simonov, Kirill},
  title =	{{Low-Rank Binary Matrix Approximation in Column-Sum Norm}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{32:1--32:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.32},
  URN =		{urn:nbn:de:0030-drops-126355},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.32},
  annote =	{Keywords: Binary Matrix Factorization, PTAS, Column-sum norm}
}
Document
Track A: Algorithms, Complexity and Games
A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion

Authors: Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh

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


Abstract
In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph (i.e., there is bipartition of V(G-S) = C ⊎ I such that C is a clique and I is an independent set in G-S). This problem is a special case of 5-Hitting Set and consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2-δ)-approximation algorithm, for any fixed δ > 0, unless the Unique Games Conjecture fails. We start by giving a simple quasipolynomial time (n^O(log n)) factor 2-approximation algorithm for SVD using the notion of clique-independent set separating collection. Thus, on the one hand SVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for any ε > 0, there is a n^O(log 1/(ε))-time 2(1+ε)-approximation algorithm.

Cite as

Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 80:1-80:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2020.80,
  author =	{Lokshtanov, Daniel and Misra, Pranabendu and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket},
  title =	{{A (2 + \epsilon)-Factor Approximation Algorithm for Split Vertex Deletion}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{80:1--80:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.80},
  URN =		{urn:nbn:de:0030-drops-124879},
  doi =		{10.4230/LIPIcs.ICALP.2020.80},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Split Vertex Deletion}
}
Document
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

Authors: Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2^{𝒪(√k)}(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2^{o(√k)}(n+m)^𝒪(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2^{𝒪(√k)}(n+m)^𝒪(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2^{𝒪(√klog k)}(n+m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width 𝒪(√k).

Cite as

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.SoCG.2020.44,
  author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
  title =	{{ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.44},
  URN =		{urn:nbn:de:0030-drops-122024},
  doi =		{10.4230/LIPIcs.SoCG.2020.44},
  annote =	{Keywords: Optimality Program, ETH, Unit Disk Graphs, Parameterized Complexity, Long Path, Long Cycle}
}
Document
Parameterization Above a Multiplicative Guarantee

Authors: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.

Cite as

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Parameterization Above a Multiplicative Guarantee. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2020.39,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterization Above a Multiplicative Guarantee}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.39},
  URN =		{urn:nbn:de:0030-drops-117248},
  doi =		{10.4230/LIPIcs.ITCS.2020.39},
  annote =	{Keywords: Parameterized Complexity, Above-Guarantee Parameterization, Girth}
}
Document
Patching Colors with Tensors

Authors: Cornelius Brand

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition. Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F_{2k+1}, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Gröbner bases, and the studied algebraic object may be of independent interest. We note that the asymptotic bound of F_{2k+1} ~~ phi^(2k) = O(2.619^k) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.

Cite as

Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{brand:LIPIcs.ESA.2019.25,
  author =	{Brand, Cornelius},
  title =	{{Patching Colors with Tensors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.25},
  URN =		{urn:nbn:de:0030-drops-111467},
  doi =		{10.4230/LIPIcs.ESA.2019.25},
  annote =	{Keywords: Color-Coding, Extensor-Coding, internal out-branching, colorful problems, algebraic algorithms, multilinear detection, deterministic algorithms, exterior algebra}
}
Document
Going Far From Degeneracy

Authors: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdős and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdős and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log{n} can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2^{O(k)}n^O(1). We complement these results by showing that the choice of degeneracy as the "above guarantee parameterization" is optimal in the following sense: For any epsilon>0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1+epsilon)d.

Cite as

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going Far From Degeneracy. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2019.47,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Going Far From Degeneracy}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.47},
  URN =		{urn:nbn:de:0030-drops-111688},
  doi =		{10.4230/LIPIcs.ESA.2019.47},
  annote =	{Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization}
}
  • Refine by Author
  • 34 Panolan, Fahad
  • 21 Saurabh, Saket
  • 12 Lokshtanov, Daniel
  • 10 Fomin, Fedor V.
  • 8 Zehavi, Meirav
  • Show More...

  • Refine by Classification
  • 11 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Theory of computation → Fixed parameter tractability
  • 4 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 7 FPT
  • 6 Parameterized Complexity
  • 4 parameterized complexity
  • 3 FPT algorithms
  • 2 Cycle Packing
  • Show More...

  • Refine by Type
  • 35 document

  • Refine by Publication Year
  • 9 2020
  • 6 2016
  • 5 2018
  • 4 2015
  • 4 2019
  • 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