LIPIcs, Volume 65
FSTTCS 2016, December 13-15, 2016, Chennai, India
Editors: Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh. Exponential-Time Approximation Schemes via Compression. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 64:1-64:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{inamdar_et_al:LIPIcs.ITCS.2024.64, author = {Inamdar, Tanmay and Kundu, Madhumita and Parviainen, Pekka and Ramanujan, M. S. and Saurabh, Saket}, title = {{Exponential-Time Approximation Schemes via Compression}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {64:1--64:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.64}, URN = {urn:nbn:de:0030-drops-195920}, doi = {10.4230/LIPIcs.ITCS.2024.64}, annote = {Keywords: Exponential-Time Algorithms, Approximation Algorithms, Graph Algorithms, Cut Problems} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Kernelization of Counting Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 77:1-77:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lokshtanov_et_al:LIPIcs.ITCS.2024.77, author = {Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav}, title = {{Kernelization of Counting Problems}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {77:1--77:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.77}, URN = {urn:nbn:de:0030-drops-196059}, doi = {10.4230/LIPIcs.ITCS.2024.77}, annote = {Keywords: Kernelization, Counting Problems} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
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)
@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} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, and Saket Saurabh. FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less. 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. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{inamdar_et_al:LIPIcs.FSTTCS.2023.28, author = {Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Ramanujan, M. S. and Saurabh, Saket}, title = {{FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {28:1--28:16}, 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.28}, URN = {urn:nbn:de:0030-drops-194013}, doi = {10.4230/LIPIcs.FSTTCS.2023.28}, annote = {Keywords: FPT-AS, F-Deletion, Packing, Elimination Distance, Elimination Treewidth} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar. On the Complexity of the Eigenvalue Deletion Problem. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{misra_et_al:LIPIcs.ISAAC.2023.53, author = {Misra, Neeldhara and Mittal, Harshil and Saurabh, Saket and Thakkar, Dhara}, title = {{On the Complexity of the Eigenvalue Deletion Problem}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {53:1--53:17}, 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.53}, URN = {urn:nbn:de:0030-drops-193555}, doi = {10.4230/LIPIcs.ISAAC.2023.53}, annote = {Keywords: Graph Modification, Rank Reduction, Eigenvalues} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bangjensen_et_al:LIPIcs.ESA.2023.13, author = {Bang-Jensen, J{\o}rgen and Klinkby, Kristine Vitting and Misra, Pranabendu and Saurabh, Saket}, title = {{A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.13}, URN = {urn:nbn:de:0030-drops-186663}, doi = {10.4230/LIPIcs.ESA.2023.13}, annote = {Keywords: Parameterized Complexity, Vertex Connectivity, Network Design} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Kernelization for Spreading Points. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ESA.2023.48, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Kernelization for Spreading Points}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {48:1--48:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.48}, URN = {urn:nbn:de:0030-drops-187017}, doi = {10.4230/LIPIcs.ESA.2023.48}, annote = {Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ESA.2023.49, author = {Fomin, Fedor V. and Le, Tien-Nam and Lokshtanov, Daniel and Saurabh, Saket and Thomass\'{e}, St\'{e}phan and Zehavi, Meirav}, title = {{Lossy Kernelization for (Implicit) Hitting Set Problems}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {49:1--49:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.49}, URN = {urn:nbn:de:0030-drops-187020}, doi = {10.4230/LIPIcs.ESA.2023.49}, annote = {Keywords: Hitting Set, Lossy Kernelization} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability). In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{inamdar_et_al:LIPIcs.ESA.2023.63, author = {Inamdar, Tanmay and Lokshtanov, Daniel and Saurabh, Saket and Surianarayanan, Vaishali}, title = {{Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability)}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {63:1--63:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.63}, URN = {urn:nbn:de:0030-drops-187167}, doi = {10.4230/LIPIcs.ESA.2023.63}, annote = {Keywords: FPT Approximation, Minimum Bisection, Unbreakable Tree Decomposition, Treewidth} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh. Fixed-Parameter Algorithms for Fair Hitting Set Problems. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{inamdar_et_al:LIPIcs.MFCS.2023.55, author = {Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Purohit, Nidhi and Saurabh, Saket}, title = {{Fixed-Parameter Algorithms for Fair Hitting Set Problems}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {55:1--55:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.55}, URN = {urn:nbn:de:0030-drops-185897}, doi = {10.4230/LIPIcs.MFCS.2023.55}, annote = {Keywords: Fairness, Parameterized Algorithms, Hitting Set} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh. Parameterized Approximation Scheme for Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jana_et_al:LIPIcs.MFCS.2023.56, author = {Jana, Satyabrata and Lokshtanov, Daniel and Mandal, Soumen and Rai, Ashutosh and Saurabh, Saket}, title = {{Parameterized Approximation Scheme for Feedback Vertex Set}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {56:1--56:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56}, URN = {urn:nbn:de:0030-drops-185902}, doi = {10.4230/LIPIcs.MFCS.2023.56}, annote = {Keywords: Feedback Vertex Set, Parameterized Approximation} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. Breaking the All Subsets Barrier for Min k-Cut. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 90:1-90:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2023.90, author = {Lokshtanov, Daniel and Saurabh, Saket and Surianarayanan, Vaishali}, title = {{Breaking the All Subsets Barrier for Min k-Cut}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {90:1--90:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.90}, URN = {urn:nbn:de:0030-drops-181422}, doi = {10.4230/LIPIcs.ICALP.2023.90}, annote = {Keywords: Exact algorithms, min k-cut, exponential algorithms, graph algorithms, k-way cut} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie}, title = {{Minimum-Membership Geometric Set Cover, Revisited}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11}, URN = {urn:nbn:de:0030-drops-178610}, doi = {10.4230/LIPIcs.SoCG.2023.11}, annote = {Keywords: geometric set cover, geometric optimization, approximation algorithms} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket}, title = {{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.12}, URN = {urn:nbn:de:0030-drops-178628}, doi = {10.4230/LIPIcs.SoCG.2023.12}, annote = {Keywords: Clustering, FPT-approximation} }
Feedback for Dagstuhl Publishing