22 Search Results for "Tale, Prafullkumar"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.28
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number

Authors: Prafullkumar Tale

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
In the Geodetic Set problem, the input consists of a graph G and a positive integer k. The goal is to determine whether there exists a subset S of vertices of size k such that every vertex in the graph is included in a shortest path between two vertices in S. Kellerhals and Koana [IPEC 2020; J. Graph Algorithms Appl 2022] proved that the problem is W[1]-hard when parameterized by the pathwidth or the feedback vertex set number of the input graph. They posed the question of whether the problem admits an XP-algorithm when parameterized by the combination of these two parameters. We answer this in the negative by proving that the problem remains NP-hard even on graphs of constant pathwidth and feedback vertex set number.
Cite as

Prafullkumar Tale. Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tale:LIPIcs.IPEC.2025.28,
  author =	{Tale, Prafullkumar},
  title =	{{Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.28},
  URN =		{urn:nbn:de:0030-drops-251601},
  doi =		{10.4230/LIPIcs.IPEC.2025.28},
  annote =	{Keywords: Geodetic Sets, NP-hardness, Constant Treewidth}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.43
A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Authors: Yashaswini Mathur and Prafullkumar Tale

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the Labeled Contractibility problem, where the input consists of two vertex-labeled graphs G and H, and the goal is to determine whether H can be obtained from G via a sequence of edge contractions. Lafond and Marchand [WADS 2025] initiated the parameterized complexity study of this problem, showing it to be W[1]-hard when parameterized by the number k of allowed contractions. They also proved that the problem is fixed-parameter tractable when parameterized by the tree-width tw of G, via an application of Courcelle’s theorem resulting in a non-constructive algorithm. In this work, we present a constructive fixed-parameter algorithm for Labeled Contractibility with running time 2^{𝒪(tw²)} ⋅ |V(G)|^{𝒪(1)}. We also prove that unless the Exponential Time Hypothesis ({ETH}) fails, it does not admit an algorithm running in time 2^{o(tw²)} ⋅ |V(G)|^{𝒪(1)}. This result adds Labeled Contractibility to a small list of problems that admit such a lower bound and matching algorithm. We further strengthen existing hardness results by showing that the problem remains NP-complete even when both input graphs have bounded maximum degree. We also investigate parameterizations by (k + δ(G)) where δ(G) denotes the degeneracy of G, and rule out the existence of subexponential-time algorithms. This answers question raised in Lafond and Marchand [WADS 2025]. We additionally provide an improved FPT algorithm with better dependence on (k + δ(G)) than previously known. Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time |V(H)|^{𝒪(|V(G)|)}, and show that this running time is optimal under {ETH}.
Cite as

Yashaswini Mathur and Prafullkumar Tale. A Finer View of the Parameterized Landscape of Labeled Graph Contractions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mathur_et_al:LIPIcs.FSTTCS.2025.43,
  author =	{Mathur, Yashaswini and Tale, Prafullkumar},
  title =	{{A Finer View of the Parameterized Landscape of Labeled Graph Contractions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.43},
  URN =		{urn:nbn:de:0030-drops-251237},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.43},
  annote =	{Keywords: Labeled Contraction, ETH Lower-bound, Treewidth, NP-hard}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.7
Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion

Authors: Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.
Cite as

Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{morelle_et_al:LIPIcs.ESA.2025.7,
  author =	{Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.7},
  URN =		{urn:nbn:de:0030-drops-244751},
  doi =		{10.4230/LIPIcs.ESA.2025.7},
  annote =	{Keywords: Graph modification problems, Parameterized complexity, Graph minors, Flat Wall theorem, Irrelevant vertex technique, Algorithmic meta-theorem, Parametric dependence, Dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.42
Broadcasting Under Structural Restrictions

Authors: Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In the Telephone Broadcast problem we are given a graph G = (V,E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).
Cite as

Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Broadcasting Under Structural Restrictions. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{egami_et_al:LIPIcs.MFCS.2025.42,
  author =	{Egami, Yudai and Gima, Tatsuya and Hanaka, Tesshu and Kobayashi, Yasuaki and Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Broadcasting Under Structural Restrictions}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.42},
  URN =		{urn:nbn:de:0030-drops-241492},
  doi =		{10.4230/LIPIcs.MFCS.2025.42},
  annote =	{Keywords: Parameterized Complexity, Structural Graph Parameters, Telephone Broadcast}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.17
Robust Contraction Decomposition for Minor-Free Graphs and Its Applications

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We prove a robust contraction decomposition theorem for H-minor-free graphs, which states that given an H-minor-free graph G and an integer p, one can partition in polynomial time the vertices of G into p sets Z₁,… ,Z_p such that tw(G/(Z_i ⧵ Z')) = O(p + |Z'|) for all i ∈ [p] and Z' ⊆ Z_i. Here, tw(⋅) denotes the treewidth of a graph and G/(Z_i ⧵ Z') denotes the graph obtained from G by contracting all edges with both endpoints in Z_i ⧵ Z'. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning E(G), and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time 2^{Õ(√k)} ⋅ n^{O(1)} or n^{O(√k)} for every vertex/edge deletion problems on H-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on H-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on H-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue. Robust Contraction Decomposition for Minor-Free Graphs and Its Applications. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2025.17,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Marx, D\'{a}niel and Misra, Pranabendu and Neuen, Daniel and Saurabh, Saket and Tale, Prafullkumar and Xue, Jie},
  title =	{{Robust Contraction Decomposition for Minor-Free Graphs and Its Applications}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.17},
  URN =		{urn:nbn:de:0030-drops-233948},
  doi =		{10.4230/LIPIcs.ICALP.2025.17},
  annote =	{Keywords: subexponential time algorithms, graph decomposition, planar graphs, minor-free graphs, graph contraction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.10
On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs

Authors: Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, and Sumedha

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In Telephone Broadcasting, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. For general graphs of n vertices, the problem is NP-complete, and the best existing algorithm has an approximation factor of 𝒪(log n/ log log n). The existence of a constant factor approximation for the general graphs is still unknown. In this paper, we study the problem in two simple families of sparse graphs, namely, cacti and graphs of bounded pathwidth. There have been several efforts to understand the complexity of the problem in cactus graphs, mostly establishing the presence of polynomial-time solutions for restricted families of cactus graphs (e.g., [Čevnik and Žerovnik, 2017; Ehresmann, 2021; Harutyunyan et al., 2009; Harutyunyan and Maraachlian, 2007; Harutyunyan and Maraachlian, 2008; Harutyunyan et al., 2023]). Despite these efforts, the complexity of the problem in arbitrary cactus graphs remained open. We settle this question by establishing the NP-completeness of telephone broadcasting in cactus graphs. For that, we show the problem is NP-complete in a simple subfamily of cactus graphs, which we call snowflake graphs. These graphs are not only cacti but also have pathwidth 2. These results establish that, despite being polynomial-time solvable in trees, the problem becomes NP-complete in very simple extensions of trees. On the positive side, we present constant-factor approximation algorithms for the studied families of graphs, namely, an algorithm with an approximation factor of 2 for cactus graphs and an approximation factor of 𝒪(1) for graphs of bounded pathwidth.
Cite as

Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, and Sumedha. On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aminian_et_al:LIPIcs.ICALP.2025.10,
  author =	{Aminian, Aida and Kamali, Shahin and Seyed-Javadi, Seyed-Mohammad and Sumedha},
  title =	{{On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.10},
  URN =		{urn:nbn:de:0030-drops-233874},
  doi =		{10.4230/LIPIcs.ICALP.2025.10},
  annote =	{Keywords: Telephone Broadcasting, Approximation Algorithms, NP-Hardness, Graph Pathwidth, Cactus Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.33
Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Authors: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set of G 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 on n vertices and a positive integer k, and asks whether there exists a resolving set of size at most k. In another metric-based graph problem, Geodetic Set, the input is a graph G and an integer k, and the objective is to determine whether there exists a subset S ⊆ V(G) of size at most k such that, for any vertex u ∈ V(G), there are two vertices s₁, s₂ ∈ S such that u lies on a shortest path from s₁ to s₂. These two classical problems are known to be intractable with respect to the natural parameter, i.e., the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. We observe that both problems admit an FPT algorithm running in 2^𝒪(vc²) ⋅ n^𝒪(1) time, and a kernelization algorithm that outputs a kernel with 2^𝒪(vc) vertices, where vc is the vertex cover number. We prove that unless the Exponential Time Hypothesis (ETH) fails, Metric Dimension and Geodetic Set, even on graphs of bounded diameter, do not admit - an FPT algorithm running in 2^o(vc²) ⋅ n^𝒪(1) time, nor - a kernelization algorithm that does not increase the solution size and outputs a kernel with 2^o(vc) vertices. We only know of one other problem in the literature that admits such a tight algorithmic lower bound with respect to vc. Similarly, the list of known problems with exponential lower bounds on the number of vertices in kernelized instances is very short.
Cite as

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension and Geodetic Set Parameterized by Vertex Cover. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{foucaud_et_al:LIPIcs.STACS.2025.33,
  author =	{Foucaud, Florent and Galby, Esther and Khazaliya, Liana and Li, Shaohua and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension and Geodetic Set Parameterized by Vertex Cover}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.33},
  URN =		{urn:nbn:de:0030-drops-228593},
  doi =		{10.4230/LIPIcs.STACS.2025.33},
  annote =	{Keywords: Parameterized Complexity, ETH-based Lower Bounds, Kernelization, Vertex Cover, Metric Dimension, Geodetic Set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.19
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

Authors: Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale

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

Abstract
Foucaud et al. [ICALP 2024] demonstrated that some problems in NP can admit (tight) double-exponential lower bounds when parameterized by treewidth or vertex cover number. They showed these first-of-their-kind results by proving conditional lower bounds for certain graph problems, in particular, the metric-based identification problems (Strong) Metric Dimension. We continue this line of research and highlight the usefulness of this type of problems, to prove relatively rare types of (tight) lower bounds. We investigate fine-grained algorithmic aspects of classical (non-metric based) identification problems in graphs, namely Locating-Dominating Set, and in set systems, namely Test Cover. In the first problem, an input is a graph G on n vertices and an integer k, and the objective is to decide whether there is a subset S of k vertices such that any two distinct vertices not in S are dominated by distinct subsets of S. In the second problem, an input is a set of items U, a collection of subsets ℱ of U called tests, and an integer k, and the objective is to select a set S of at most k tests such that any two distinct items are contained in a distinct subset of tests of S. For our first result, we adapt the techniques introduced by Foucaud et al. [ICALP 2024] to prove similar (tight) lower bounds for these two problems. - Locating-Dominating Set (respectively, Test Cover) parameterized by the treewidth of the input graph (respectively, the natural auxiliary graph) does not admit an algorithm running in time 2^{2^o(tw)} ⋅ poly(n) (respectively, 2^{2^o(tw)} ⋅ poly(|U| + |ℱ|))), unless the ETH fails. This augments the short list of NP-Complete problems that admit tight double-exponential lower bounds when parameterized by treewidth, and shows that "local" (non-metric-based) problems can also admit such bounds. We show that these lower bounds are tight by designing treewidth-based dynamic programming schemes with matching running times. Next, we prove that these two problems also admit "exotic" (and tight) lower bounds, when parameterized by the solution size k. We prove that unless the ETH fails, - Locating-Dominating Set does not admit an algorithm running in time 2^o(k²) ⋅ poly(n), nor a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with 2^o(k) vertices, and - Test Cover does not admit an algorithm running in time 2^{2^o(k)} ⋅ poly(|U| + |ℱ|) nor a kernel with 2^{2^o(k)} vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times. To the best of our knowledge, Locating-Dominating Set is the first known problem which is FPT when parameterized by solution size k, where the optimal running time has a quadratic function in the exponent. These results also extend the (very) small list of problems that admit an ETH-based lower bound on the number of vertices in a kernel, and (for Test Cover) a double-exponential lower bound when parameterized by the solution size. Whereas it is the first example, to the best of our knowledge, that admit a double exponential lower bound for the number of vertices.
Cite as

Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2024.19,
  author =	{Chakraborty, Dipayan and Foucaud, Florent and Majumdar, Diptapriyo and Tale, Prafullkumar},
  title =	{{Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.19},
  URN =		{urn:nbn:de:0030-drops-221469},
  doi =		{10.4230/LIPIcs.ISAAC.2024.19},
  annote =	{Keywords: Identification Problems, Locating-Dominating Set, Test Cover, Double Exponential Lower Bound, ETH, Kernelization Lower Bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.66
Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover

Authors: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

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

Abstract
Treewidth serves as an important parameter that, when bounded, yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and Quantified SAT or, more generally, Quantified CSP, are fixed-parameter tractable parameterized by the treewidth {of the input’s (primal) graph} plus the length of the MSO-formula [Courcelle, Information & Computation 1990] and the quantifier rank [Chen, ECAI 2004], respectively. The algorithms generated by these (meta-)results have running times whose dependence on treewidth is a tower of exponents. A conditional lower bound by Fichte, Hecher, and Pfandler [LICS 2020] shows that, for Quantified SAT, the height of this tower is equal to the number of quantifier alternations. These types of lower bounds, which show that at least double-exponential factors in the running time are necessary, exhibit the extraordinary level of computational hardness for such problems, and are rare in the current literature: there are only a handful of such lower bounds (for treewidth and vertex cover parameterizations) and all of them are for problems that are #NP-complete, Σ₂^p-complete, Π₂^p-complete, or complete for even higher levels of the polynomial hierarchy. Our results demonstrate, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to achieve double-exponential lower bounds: we derive double-exponential lower bounds in the treewidth (tw) and the vertex cover number (vc), for natural, important, and well-studied NP-complete graph problems. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: Metric Dimension, Strong Metric Dimension, and Geodetic Set. We prove that these problems do not admit 2^{2^o(tw)}⋅n^𝒪(1)-time algorithms, even on bounded diameter graphs, unless the ETH fails (here, n is the number of vertices in the graph). In fact, for Strong Metric Dimension, the double-exponential lower bound holds even for the vertex cover number. We further complement all our lower bounds with matching (and sometimes non-trivial) upper bounds. For the conditional lower bounds, we design and use a novel, yet simple technique based on Sperner families of sets. We believe that the amenability of our technique will lead to obtaining such lower bounds for many other problems in NP.
Cite as

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{foucaud_et_al:LIPIcs.ICALP.2024.66,
  author =	{Foucaud, Florent and Galby, Esther and Khazaliya, Liana and Li, Shaohua and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.66},
  URN =		{urn:nbn:de:0030-drops-202091},
  doi =		{10.4230/LIPIcs.ICALP.2024.66},
  annote =	{Keywords: Parameterized Complexity, ETH-based Lower Bounds, Double-Exponential Lower Bounds, Kernelization, Vertex Cover, Treewidth, Diameter, Metric Dimension, Strong Metric Dimension, Geodetic Sets}
}
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.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.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.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.FSTTCS.2022.27
Romeo and Juliet Meeting in Forest like Regions

Authors: Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k ≥ 1 agents. While the initial positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. Fomin, Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is PSPACE-hard and co-W[2]-hard parameterized by the number of agents. This hardness naturally motivates the structural parameterization of the problem. The authors proved that it admits an FPT algorithm when parameterized by the modular width and the number of allowed rounds. However, they left open the complexity of the problem from the perspective of other structural parameters. In particular, they explicitly asked whether the problem admits an FPT or XP-algorithm with respect to the treewidth of the input graph. We answer this question in the negative and show that Rendezvous is co-NP-hard even for graphs of constant treewidth. Further, we show that the problem is co-W[1]-hard when parameterized by the feedback vertex set number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized by the vertex cover number and the number of agents. Complementing these hardness results, we show that the Rendezvous is FPT when parameterized by both the vertex cover number and the solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can be solved in polynomial time.
Cite as

Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami. Romeo and Juliet Meeting in Forest like Regions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.FSTTCS.2022.27,
  author =	{Misra, Neeldhara and Mulpuri, Manas and Tale, Prafullkumar and Viramgami, Gaurav},
  title =	{{Romeo and Juliet Meeting in Forest like Regions}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.27},
  URN =		{urn:nbn:de:0030-drops-174194},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.27},
  annote =	{Keywords: Games on Graphs, Dynamic Separators, W\lbrack1\rbrack-hardness, Structural Parametersization, Treewidth}
}
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.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.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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.87
Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

Authors: Tuukka Korhonen

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute with max and + operations. For a graph G, an MWIS-circuit of G is a tropical circuit whose inputs correspond to vertices of G and which computes the weight of a maximum weight independent set of G for any assignment of weights to the inputs. We show that if G has treewidth w and maximum degree d, then any MWIS-circuit of G has 2^{Ω(w/d)} gates and that if G is planar, or more generally H-minor-free for any fixed graph H, then any MWIS-circuit of G has 2^{Ω(w)} gates. An MWIS-formula is an MWIS-circuit where each gate has fan-out at most one. We show that if G has treedepth t and maximum degree d, then any MWIS-formula of G has 2^{Ω(t/d)} gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and H-minor-free graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.
Cite as

Tuukka Korhonen. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{korhonen:LIPIcs.ICALP.2021.87,
  author =	{Korhonen, Tuukka},
  title =	{{Lower Bounds on Dynamic Programming for Maximum Weight Independent Set}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.87},
  URN =		{urn:nbn:de:0030-drops-141562},
  doi =		{10.4230/LIPIcs.ICALP.2021.87},
  annote =	{Keywords: Maximum weight independent set, Treewidth, Tropical circuits, Dynamic programming, Treedepth, Monotone circuit complexity}
}
  • Refine by Type
  • 22 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 7 2025
  • 2 2024
  • 1 2023
  • 4 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 18 Tale, Prafullkumar
  • 6 Saurabh, Saket
  • 5 Sharma, Roohani
  • 4 Galby, Esther
  • 3 Foucaud, Florent
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Theory of computation → Fixed parameter tractability
  • 4 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 4 Parameterized Complexity
  • 4 Treewidth
  • 3 Kernelization
  • 3 Metric Dimension
  • 3 parameterized complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact