21 Search Results for "Sharma, Roohani"

Document
DOI: 10.4230/DagRep.13.8.1
Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Authors: George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.
Cite as

George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331). In Dagstuhl Reports, Volume 13, Issue 8, pp. 1-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{karypis_et_al:DagRep.13.8.1,
  author =	{Karypis, George and Schulz, Christian and Strash, Darren and Ajwani, Deepak and Bisseling, Rob H. and Casel, Katrin and \c{C}ataly\"{u}rek, \"{U}mit V. and Chevalier, C\'{e}dric and Chudigiewitsch, Florian and Faraj, Marcelo Fonseca and Fellows, Michael and Gottesb\"{u}ren, Lars and Heuer, Tobias and Kaya, Kamer and Lacki, Jakub and Langguth, Johannes and Li, Xiaoye Sherry and Mayer, Ruben and Meintrup, Johannes and Mizutani, Yosuke and Pellegrini, Fran\c{c}ois and Petrini, Fabrizio and Rosamond, Frances and Safro, Ilya and Schlag, Sebastian and Sharma, Roohani and Sullivan, Blair D. and U\c{c}ar, Bora and Yzelman, Albert-Jan},
  title =	{{Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)}},
  pages =	{1--45},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Karypis, George and Schulz, Christian and Strash, Darren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.1},
  URN =		{urn:nbn:de:0030-drops-198114},
  doi =		{10.4230/DagRep.13.8.1},
  annote =	{Keywords: combinatorial optimization, experimental algorithmics, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.5
Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity

Authors: Sriram Bhyravarapu, Satyabrata Jana, Saket Saurabh, and Roohani Sharma

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

Abstract
We consider the question of polynomial kernelization of a generalization of the classical Vertex Cover problem parameterized by a parameter that is provably smaller than the solution size. In particular, we focus on the c-Component Order Connectivity problem (c-COC) where given an undirected graph G and a non-negative integer t, the objective is to test whether there exists a set S of size at most t such that every component of G-S contains at most c vertices. Such a set S is called a c-coc set. It is known that c-COC admits a kernel with {O}(ct) vertices. Observe that for c = 1, this corresponds to the Vertex Cover problem. We study the c-Component Order Connectivity problem parameterized by the size of a d-coc set (c-COC/d-COC), where c,d ∈ ℕ with c ≤ d. In particular, the input is an undirected graph G, a positive integer t and a set M of at most k vertices of G, such that the size of each connected component in G - M is at most d. The question is to find a set S of vertices of size at most t, such that the size of each connected component in G - S is at most c. In this paper, we give a kernel for c-COC/d-COC with O(k^{d-c+1}) vertices and O(k^{d-c+2}) edges. Our result exhibits that the difference in d and c, and not their absolute values, determines the exact degree of the polynomial in the kernel size. When c = d = 1, the c-COC/d-COC problem is exactly the Vertex Cover problem parameterized by the solution size, which has a kernel with O(k) vertices and O(k²) edges, and this is asymptotically tight [Dell & Melkebeek, JACM 2014]. We also show that the dependence of d-c in the exponent of the kernel size cannot be avoided under reasonable complexity assumptions.
Cite as

Sriram Bhyravarapu, Satyabrata Jana, Saket Saurabh, and Roohani Sharma. Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.IPEC.2023.5,
  author =	{Bhyravarapu, Sriram and Jana, Satyabrata and Saurabh, Saket and Sharma, Roohani},
  title =	{{Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.5},
  URN =		{urn:nbn:de:0030-drops-194241},
  doi =		{10.4230/LIPIcs.IPEC.2023.5},
  annote =	{Keywords: Kernelization, Component Order Connectivity, Vertex Cover, Structural Parameterizations}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.11
Parameterized Complexity Classification for Interval Constraints

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

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

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

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

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.IPEC.2023.11,
  author =	{Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Pilipczuk, Marcin and Sharma, Roohani},
  title =	{{Parameterized Complexity Classification for Interval Constraints}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.11},
  URN =		{urn:nbn:de:0030-drops-194306},
  doi =		{10.4230/LIPIcs.IPEC.2023.11},
  annote =	{Keywords: (minimum) constraint satisfaction problem, Allen’s interval algebra, parameterized complexity, cut problems}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.17
Approximate Monotone Local Search for Weighted Problems

Authors: Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma

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

Abstract
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover, d-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most α ⋅ W (and of arbitrary cardinality) in time c^k ⋅ n^{𝒪(1)} where W is the minimum weight of a solution of cardinality at most k. In the unweighted setting, Esmer et al. determine the smallest value d for which a β-approximation algorithm running in time dⁿ ⋅ n^{𝒪(1)} can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed ε > 0 we obtain a β-approximation algorithm running in time 𝒪((d+ε)ⁿ), for the same d as in the unweighted setting. Similarly, we also extend a β-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time β-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted d-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.
Cite as

Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Approximate Monotone Local Search for Weighted Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{esmer_et_al:LIPIcs.IPEC.2023.17,
  author =	{Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
  title =	{{Approximate Monotone Local Search for Weighted Problems}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{17:1--17:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.17},
  URN =		{urn:nbn:de:0030-drops-194360},
  doi =		{10.4230/LIPIcs.IPEC.2023.17},
  annote =	{Keywords: parameterized approximations, exponential approximations, monotone local search}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.8
Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

Authors: R. Krithika, V. K. Kutty Malu, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
A bipartite graph is called a biclique if it is a complete bipartite graph and a biclique is called a balanced biclique if it has equal number of vertices in both parts of its bipartition. In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) unless NP ⊆ coNP/poly.
Cite as

R. Krithika, V. K. Kutty Malu, Roohani Sharma, and Prafullkumar Tale. Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{krithika_et_al:LIPIcs.FSTTCS.2023.8,
  author =	{Krithika, R. and Malu, V. K. Kutty and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-193811},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.8},
  annote =	{Keywords: contraction, bicliques, balanced bicliques, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.40
Structural Parameterizations of b-Coloring

Authors: Lars Jaffke, Paloma T. Lima, and Roohani Sharma

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized by the vertex cover number and XP and 𝖶[1]-hard parameterized by clique-width. Its complexity when parameterized by the treewidth of the input graph remained an open problem. We settle this question by showing that b-Coloring is XNLP-complete when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is 𝖶[t]-hard for all t, and resolves the parameterized complexity of b-Coloring parameterized by treewidth. We complement this result by showing that b-Coloring is FPT when parameterized by neighborhood diversity and by twin cover, two parameters that generalize vertex cover to more dense graphs, but are incomparable to pathwidth.
Cite as

Lars Jaffke, Paloma T. Lima, and Roohani Sharma. Structural Parameterizations of b-Coloring. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.ISAAC.2023.40,
  author =	{Jaffke, Lars and Lima, Paloma T. and Sharma, Roohani},
  title =	{{Structural Parameterizations of b-Coloring}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.40},
  URN =		{urn:nbn:de:0030-drops-193429},
  doi =		{10.4230/LIPIcs.ISAAC.2023.40},
  annote =	{Keywords: b-coloring, structural parameterization, XNLP, pathwidth, neighborhood diversity, twin cover}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.14
Domination and Cut Problems on Chordal Graphs with Bounded Leafage

Authors: Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale

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

Abstract
The leafage of a chordal graph G is the minimum integer 𝓁 such that G can be realized as an intersection graph of subtrees of a tree with 𝓁 leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1). We present a conceptually much simpler algorithm that runs in time 2^𝒪(𝓁) ⋅ n^𝒪(1). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n^𝒪(𝓁)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n^O(1)-time.
Cite as

Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. Domination and Cut Problems on Chordal Graphs with Bounded Leafage. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.IPEC.2022.14,
  author =	{Galby, Esther and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Domination and Cut Problems on Chordal Graphs with Bounded Leafage}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.14},
  URN =		{urn:nbn:de:0030-drops-173704},
  doi =		{10.4230/LIPIcs.IPEC.2022.14},
  annote =	{Keywords: Chordal Graphs, Leafage, FPT Algorithms, Dominating Set, MultiCut with Undeletable Terminals, Multiway Cut with Undeletable Terminals}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.50
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Authors: Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma

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

Abstract
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a non-empty set family over a universe of size n which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use approximate monotone local search to show that a parameterized α-approximation algorithm that runs in c^k⋅n^𝒪(1) time, where k is the solution size, can be used to derive an α-approximation randomized algorithm that runs in dⁿ⋅n^𝒪(1) time, where d is the unique value in (1, 1+{c-1}/α) such that 𝒟(1/α‖{d-1}/{c-1}) = {ln c}/α and 𝒟(a‖b) is the Kullback-Leibler divergence. This running time matches that of Fomin et al. for α = 1, and is strictly better when α > 1, for any c > 1. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We use an approximate variant of the exhaustive search as a benchmark for our algorithm. We show that the classic 2ⁿ⋅n^𝒪(1) exhaustive search can be adapted to an α-approximate exhaustive search that runs in time (1+exp(-α⋅ℋ(1/(α))))ⁿ⋅n^𝒪(1), where ℋ is the entropy function. Furthermore, we provide a lower bound stating that the running time of this α-approximate exhaustive search is the best achievable running time in an oracle model. When compared to approximate exhaustive search, and to other techniques, the running times obtained by approximate monotone local search are strictly better for any α ≥ 1, c > 1. We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1-approximation algorithm for Vertex Cover with running time 1.114ⁿ⋅n^𝒪(1), improving upon the previously best known 1.1-approximation running in time 1.127ⁿ⋅n^𝒪(1) by Bourgeois et al. [DAM 2011].
Cite as

Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50,
  author =	{Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
  title =	{{Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.50},
  URN =		{urn:nbn:de:0030-drops-169887},
  doi =		{10.4230/LIPIcs.ESA.2022.50},
  annote =	{Keywords: parameterized approximations, exponential approximations, monotone local search}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.51
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Authors: Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.
Cite as

Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.MFCS.2022.51,
  author =	{Galby, Esther and Khazaliya, Liana and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.51},
  URN =		{urn:nbn:de:0030-drops-168496},
  doi =		{10.4230/LIPIcs.MFCS.2022.51},
  annote =	{Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.69
Reducing the Vertex Cover Number via Edge Contractions

Authors: Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: - Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. - It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem. - Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).
Cite as

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2022.69,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S. and Tale, Prafullkumar},
  title =	{{Reducing the Vertex Cover Number via Edge Contractions}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.69},
  URN =		{urn:nbn:de:0030-drops-168671},
  doi =		{10.4230/LIPIcs.MFCS.2022.69},
  annote =	{Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.12
Parameterized Complexity of Directed Spanner Problems

Authors: Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, and Roohani Sharma

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

Abstract
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has a multiplicative t-spanner with at most m-k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most m-k arcs. We show that - Directed Multiplicative Spanner admits a polynomial kernel of size 𝒪(k⁴t⁵) and can be solved in randomized (4t)^k⋅ n^𝒪(1) time, - Directed Additive Spanner is W[1]-hard when parameterized by k even if t = 1 and the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is FPT when parameterized by t and k.
Cite as

Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, and Roohani Sharma. Parameterized Complexity of Directed Spanner Problems. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.IPEC.2020.12,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani},
  title =	{{Parameterized Complexity of Directed Spanner Problems}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{12:1--12:11},
  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.12},
  URN =		{urn:nbn:de:0030-drops-133156},
  doi =		{10.4230/LIPIcs.IPEC.2020.12},
  annote =	{Keywords: Graph spanners, directed graphs, parameterized complexity, 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-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
DOI: 10.4230/LIPIcs.MFCS.2020.75
On the Parameterized Complexity of Deletion to ℋ-Free Strong Components

Authors: Rian Neogi, M. S. Ramanujan, Saket Saurabh, and Roohani Sharma

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

Abstract
Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the ℋ-SCC Deletion problem. Here, one is given a digraph D, an integer k and the objective is to decide whether there is a vertex set of size at most k whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ℋ as (not necessarily induced) subgraphs. When ℋ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ℋ only contains rooted graphs or if ℋ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].
Cite as

Rian Neogi, M. S. Ramanujan, Saket Saurabh, and Roohani Sharma. On the Parameterized Complexity of Deletion to ℋ-Free Strong Components. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{neogi_et_al:LIPIcs.MFCS.2020.75,
  author =	{Neogi, Rian and Ramanujan, M. S. and Saurabh, Saket and Sharma, Roohani},
  title =	{{On the Parameterized Complexity of Deletion to ℋ-Free Strong Components}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{75:1--75:13},
  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.75},
  URN =		{urn:nbn:de:0030-drops-127444},
  doi =		{10.4230/LIPIcs.MFCS.2020.75},
  annote =	{Keywords: Directed Cut Problems, Fixed-parameter Tractability, DFVS}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.47
Fault Tolerant Subgraphs with Applications in Kernelization

Authors: William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi

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

Abstract
In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as fewest arcs/vertices as possible such that, after the failure of any set F of at most k ≥ 1 arcs, testing whether D-F has a certain property P is equivalent to testing whether H-F has that property. Here, reachability (or, more generally, distance preservation) is the most basic requirement to maintain to ensure that the network functions properly. Given a vertex s ∈ V(D), Baswana et al. [STOC'16] presented a construction of H with O(2^kn) arcs in time O(2^{k}nm) where n=|V(D)| and m= |E(D)| such that for any vertex v ∈ V(D): if there exists a path from s to v in D-F, then there also exists a path from s to v in H-F. Additionally, they gave a tight matching lower bound. While the question of the improvement of the dependency on k arises for special classes of digraphs, an arguably more basic research direction concerns the dependency on n (for reachability between a pair of vertices s,t ∈ V(D)) - which are the largest classes of digraphs where the dependency on n can be made sublinear, logarithmic or even constant? Already for the simple classes of directed paths and tournaments, Ω(n) arcs are mandatory. Nevertheless, we prove that "almost acyclicity" suffices to eliminate the dependency on n entirely for a broad class of dense digraphs called bounded independence digraphs. Also, the dependence in k is only a polynomial factor for this class of digraphs. In fact, our sparsification procedure extends to preserve parity-based reachability. Additionally, it finds notable applications in Kernelization: we prove that the classic Directed Feedback Arc Set (DFAS) problem as well as Directed Edge Odd Cycle Transversal (DEOCT) (which, in sharp contrast to DFAS, is W[1]-hard on general digraphs) admit polynomial kernels on bounded independence digraphs. In fact, for any p ∈ N, we can design a polynomial kernel for the problem of hitting all cycles of length ℓ where (ℓ mod p = 1). As a complementary result, we prove that DEOCT is NP-hard on tournaments by establishing a combinatorial identity between the minimum size of a feedback arc set and the minimum size of an edge odd cycle transversal. In passing, we also improve upon the running time of the sub-exponential FPT algorithm for DFAS in digraphs of bounded independence number given by Misra et at. [FSTTCS 2018], and give the first sub-exponential FPT algorithm for DEOCT in digraphs of bounded independence number.
Cite as

William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Fault Tolerant Subgraphs with Applications in Kernelization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lochet_et_al:LIPIcs.ITCS.2020.47,
  author =	{Lochet, William and Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
  title =	{{Fault Tolerant Subgraphs with Applications in Kernelization}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{47:1--47:22},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.47},
  URN =		{urn:nbn:de:0030-drops-117326},
  doi =		{10.4230/LIPIcs.ITCS.2020.47},
  annote =	{Keywords: sparsification, kernelization, fault tolerant subgraphs, directed feedback arc set, directed edge odd cycle transversal, bounded independence number digraphs}
}
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-dev.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}
}
  • Refine by Author
  • 20 Sharma, Roohani
  • 11 Saurabh, Saket
  • 6 Zehavi, Meirav
  • 4 Misra, Pranabendu
  • 4 Tale, Prafullkumar
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Parameterized complexity and exact algorithms
  • 6 Theory of computation → Fixed parameter tractability
  • 3 Mathematics of computing → Approximation algorithms
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 5 parameterized complexity
  • 3 kernelization
  • 2 Parameterized Complexity
  • 2 directed feedback arc set
  • 2 exponential approximations
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 5 2023
  • 4 2020
  • 4 2022
  • 3 2018
  • 2 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact