183 Search Results for "Lokshtanov, Daniel"

Volume

LIPIcs, Volume 289

41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

STACS 2024, March 12-14, 2024, Clermont-Ferrand, France

Editors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov

Volume

LIPIcs, Volume 89

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

IPEC 2017, September 6-8, 2017, Vienna, Austria

Editors: Daniel Lokshtanov and Naomi Nishimura

Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.24
When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection

Authors: Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
Classical work on metric space based committee selection problem interprets distance as "near is better". In this work, motivated by real-life situations, we interpret distance as "far is better". Formally stated, we initiate the study of "obnoxious" committee scoring rules when the voters' preferences are expressed via a metric space. To accomplish this, we propose a model where large distances imply high satisfaction (in contrast to the classical setting where shorter distances imply high satisfaction) and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value λ between 1 and k, the committee size, a voter derives satisfaction from only the λth favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of λ = 1, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a d-dimensional Euclidean space. We show that when λ is 1 and k, the problem is polynomial-time solvable in ℝ² and general metric space, respectively. However, for λ = k-1, it is NP-hard even in ℝ². Thus, we have "double-dichotomy" in ℝ² with respect to the value of λ, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be "tight" for ℝ² because the problem is NP-hard for general metric space, even for λ = 1. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.
Cite as

Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2024.24,
  author =	{Gupta, Sushmita and Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
  title =	{{When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.24},
  URN =		{urn:nbn:de:0030-drops-222135},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.24},
  annote =	{Keywords: Metric Space, Parameterized Complexity, Approximation, Obnoxious Facility Location}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.6
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3

Authors: Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi

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

Abstract
In a disk graph, every vertex corresponds to a disk in ℝ² and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes both planar graphs and unit-disk graphs. We study a fundamental optimization problem in algorithmic graph theory, Bipartization (also known as Odd Cycle Transversal), on the class of disk graphs. The goal of Bipartization is to delete a minimum number of vertices from the input graph such that the resulting graph is bipartite. A folklore (polynomial-time) 3-approximation algorithm for Bipartization on disk graphs follows from the classical framework of Goemans and Williamson [Combinatorica'98] for cycle-hitting problems. For over two decades, this result has remained the best known approximation for the problem (in fact, even for Bipartization on unit-disk graphs). In this paper, we achieve the first improvement upon this result, by giving a (3-α)-approximation algorithm for Bipartization on disk graphs, for some constant α > 0. Our algorithm directly generalizes to the broader class of pseudo-disk graphs. Furthermore, our algorithm is robust in the sense that it does not require a geometric realization of the input graph to be given.
Cite as

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.APPROX/RANDOM.2024.6,
  author =	{Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav},
  title =	{{Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.6},
  URN =		{urn:nbn:de:0030-drops-209990},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.6},
  annote =	{Keywords: bipartization, geometric intersection graphs, approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.34
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness

Authors: Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski

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

Abstract
It is known for many algorithmic problems that if a tree decomposition of width t is given in the input, then the problem can be solved with exponential dependence on t. A line of research initiated by Lokshtanov, Marx, and Saurabh [SODA 2011] produced lower bounds showing that in many cases known algorithms already achieve the best possible exponential dependence on t, assuming the Strong Exponential-Time Hypothesis (SETH). The main message of this paper is showing that the same lower bounds can already be obtained in a much more restricted setting: informally, a graph consisting of a block of t vertices connected to components of constant size already has the same hardness as a general tree decomposition of width t. Formally, a (σ,δ)-hub is a set Q of vertices such that every component of Q has size at most σ and is adjacent to at most δ vertices of Q. We explore if the known tight lower bounds parameterized by the width of the given tree decomposition remain valid if we parameterize by the size of the given hub. - For every ε > 0, there are σ,δ > 0 such that Independent Set (equivalently Vertex Cover) cannot be solved in time (2-ε)^p⋅ n, even if a (σ, δ)-hub of size p is given in the input, assuming the SETH. This matches the earlier tight lower bounds parameterized by width of the tree decomposition. Similar tight bounds are obtained for Odd Cycle Transversal, Max Cut, q-Coloring, and edge/vertex deletions versions of q-Coloring. - For every ε > 0, there are σ,δ > 0 such that △-Partition cannot be solved in time (2-ε)^p ⋅ n, even if a (σ, δ)-hub of size p is given in the input, assuming the Set Cover Conjecture (SCC). In fact, we prove that this statement is equivalent to the SCC, thus it is unlikely that this could be proved assuming the SETH. - For Dominating Set, we can prove a non-tight lower bound ruling out (2-ε)^p ⋅ n^𝒪(1) algorithms, assuming either the SETH or the SCC, but this does not match the 3^p⋅ n^{𝒪(1)} upper bound. Thus our results reveal that, for many problems, the research on lower bounds on the dependence on tree width was never really about tree decompositions, but the real source of hardness comes from a much simpler structure. Additionally, we study if the same lower bounds can be obtained if σ and δ are fixed universal constants (not depending on ε). We show that lower bounds of this form are possible for Max Cut and the edge-deletion version of q-Coloring, under the Max 3-Sat Hypothesis (M3SH). However, no such lower bounds are possible for Independent Set, Odd Cycle Transversal, and the vertex-deletion version of q-Coloring: better than brute force algorithms are possible for every fixed (σ,δ).
Cite as

Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2024.34,
  author =	{Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{34:1--34:17},
  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.34},
  URN =		{urn:nbn:de:0030-drops-201772},
  doi =		{10.4230/LIPIcs.ICALP.2024.34},
  annote =	{Keywords: Parameterized Complexity, Tight Bounds, Hub, Treewidth, Strong Exponential Time Hypothesis, Vertex Coloring, Vertex Deletion, Edge Deletion, Triangle Packing, Triangle Partition, Set Cover Hypothesis, Dominating Set}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.88
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

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

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

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

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

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88,
  author =	{Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya},
  title =	{{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{88:1--88:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88},
  URN =		{urn:nbn:de:0030-drops-202318},
  doi =		{10.4230/LIPIcs.ICALP.2024.88},
  annote =	{Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.72
A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs

Authors: Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Vertex Cover is a fundamental optimization problem, and is among Karp’s 21 NP-complete problems. The problem aims to compute, for a given graph G, a minimum-size set S of vertices of G such that G - S contains no edge. Vertex Cover admits a simple polynomial-time 2-approximation algorithm, which is the best approximation ratio one can achieve in polynomial time, assuming the Unique Game Conjecture. However, on many restrictive graph classes, it is possible to obtain better-than-2 approximation in polynomial time (or even PTASes) for Vertex Cover. In the club of geometric intersection graphs, examples of such graph classes include unit-disk graphs, disk graphs, pseudo-disk graphs, rectangle graphs, etc. In this paper, we study Vertex Cover on the broadest class of geometric intersection graphs in the plane, known as string graphs, which are intersection graphs of any connected geometric objects in the plane. Our main result is a polynomial-time 1.9999-approximation algorithm for Vertex Cover on string graphs, breaking the natural 2 barrier. Prior to this work, no better-than-2 approximation (in polynomial time) was known even for special cases of string graphs, such as intersection graphs of segments. Our algorithm is simple, robust (in the sense that it does not require the geometric realization of the input string graph to be given), and also works for the weighted version of Vertex Cover. Due to a connection between approximation for Independent Set and approximation for Vertex Cover observed by Har-Peled, our result can be viewed as a first step towards obtaining constant-approximation algorithms for Independent Set on string graphs.
Cite as

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 72:1-72:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.SoCG.2024.72,
  author =	{Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav},
  title =	{{A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{72:1--72:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.72},
  URN =		{urn:nbn:de:0030-drops-200174},
  doi =		{10.4230/LIPIcs.SoCG.2024.72},
  annote =	{Keywords: vertex cover, geometric intersection graphs, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.11
Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like Triangle Hitting (TH), Feedback Vertex Set (FVS) or Odd Cycle Transversal (OCT). These problems respectively ask for the existence in a graph G of a set X of at most k vertices such that G-X is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form 2^o(k)n^𝒪(1) exist in planar and even H-minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized "fat" objects ([Fomin et al. 2012], [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]). In this paper we first identify sufficient conditions, for any graph class 𝒞 included in string graphs, to admit subexponential FPT algorithms for any problem in 𝒫, a family of bidimensional problems where one has to find a set of size at most k hitting a fixed family of graphs, containing in particular FVS. Informally, these conditions boil down to the fact that for any G ∈ 𝒞, the local radius of G (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of G and in the maximum matching in the neighborhood of a vertex. To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem Π ∈ 𝒫 (in particular, FVS) can be solved in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(k^{9/10}log k) n^𝒪(1) in intersection graphs of axis-parallel squares On the positive side, we also provide positive results for TH by solving it in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(√dt²(log t)k^{2/3}log k) n^𝒪(1)-time in K_{t,t}-free d-DIR graphs (intersection of segments with d slopes) On the negative side, assuming the ETH we rule out the existence of algorithms solving: - TH and OCT in time 2^o(n) in 2-DIR graphs and more generally in time 2^o(√{Δn}) in 2-DIR graphs with maximum degree Δ, and - TH, FVS, and OCT in time 2^o(√n) in K_{2,2}-free contact-2-DIR graphs of maximum degree 6. Observe that together, these results show that the absence of large K_{t,t} is a necessary and sufficient condition for the existence of subexponential FPT algorithms for TH in 2-DIR.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.SWAT.2024.11,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.11},
  URN =		{urn:nbn:de:0030-drops-200519},
  doi =		{10.4230/LIPIcs.SWAT.2024.11},
  annote =	{Keywords: geometric intersection graphs, subexponential FPT algorithms, cycle-hitting problems, bidimensionality}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2024
LIPIcs, Volume 289, STACS 2024, Complete Volume

Authors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov

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

Abstract
LIPIcs, Volume 289, STACS 2024, Complete Volume
Cite as

41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 1-1048, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{beyersdorff_et_al:LIPIcs.STACS.2024,
  title =	{{LIPIcs, Volume 289, STACS 2024, Complete Volume}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{1--1048},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024},
  URN =		{urn:nbn:de:0030-drops-197098},
  doi =		{10.4230/LIPIcs.STACS.2024},
  annote =	{Keywords: LIPIcs, Volume 289, STACS 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beyersdorff_et_al:LIPIcs.STACS.2024.0,
  author =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.0},
  URN =		{urn:nbn:de:0030-drops-197108},
  doi =		{10.4230/LIPIcs.STACS.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2024.1
Polynomial-Time Pseudodeterministic Constructions (Invited Talk)

Authors: Igor C. Oliveira

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

Abstract
A randomised algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser (2011) posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomised algorithm B such that, for infinitely many values of n, B(1ⁿ) outputs a canonical n-bit prime p_n with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time pseudodeterministic construction of Oliveira and Santhanam (2017). This talk will cover the main ideas behind these constructions and discuss their implications, such as the existence of infinitely many primes with succinct and efficient representations.
Cite as

Igor C. Oliveira. Polynomial-Time Pseudodeterministic Constructions (Invited Talk). In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{oliveira:LIPIcs.STACS.2024.1,
  author =	{Oliveira, Igor C.},
  title =	{{Polynomial-Time Pseudodeterministic Constructions}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.1},
  URN =		{urn:nbn:de:0030-drops-197112},
  doi =		{10.4230/LIPIcs.STACS.2024.1},
  annote =	{Keywords: Pseudorandomness, Explicit Constructions, Pseudodeterministic Algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2024.2
The Role of Local Algorithms in Privacy (Invited Talk)

Authors: Sofya Raskhodnikova

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

Abstract
We will discuss research areas at the intersection of local algorithms and differential privacy. The main focus will be on using local Lipschitz filters to enable black-box differentially private queries to sensitive datasets. We will also cover new sublinear computational tasks arising in private data analysis. Finally, we will touch upon distributed models of privacy.
Cite as

Sofya Raskhodnikova. The Role of Local Algorithms in Privacy (Invited Talk). In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{raskhodnikova:LIPIcs.STACS.2024.2,
  author =	{Raskhodnikova, Sofya},
  title =	{{The Role of Local Algorithms in Privacy}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.2},
  URN =		{urn:nbn:de:0030-drops-197123},
  doi =		{10.4230/LIPIcs.STACS.2024.2},
  annote =	{Keywords: Sublinear algorithms, differential privacy, reconstruction of Lipschitz functions, local algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2024.3
Structurally Tractable Graph Classes (Invited Talk)

Authors: Szymon Toruńczyk

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

Abstract
Sparsity theory, initiated by Ossona de Mendez and Nešetřil, identifies those classes of sparse graphs that are tractable in various ways - algorithmically, combinatorially, and logically - as exactly the nowhere dense classes. An ongoing effort aims at generalizing sparsity theory to classes of graphs that are not necessarily sparse. Twin-width theory, developed by Bonnet, Thomassé and co-authors, is a step in that direction. A theory unifying the two is anticipated. It is conjectured that the relevant notion characterising dense graph classes that are tractable, generalising nowhere denseness and bounded twin-width, is the notion of a monadically dependent class, introduced by Shelah in model theory. I will survey the recent, rapid progress in the understanding of those classes, and of the related monadically stable classes. This development combines tools from structural graph theory, logic (finite and infinite model theory), and algorithms (parameterised algorithms and range search queries).
Cite as

Szymon Toruńczyk. Structurally Tractable Graph Classes (Invited Talk). In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{torunczyk:LIPIcs.STACS.2024.3,
  author =	{Toru\'{n}czyk, Szymon},
  title =	{{Structurally Tractable Graph Classes}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.3},
  URN =		{urn:nbn:de:0030-drops-197134},
  doi =		{10.4230/LIPIcs.STACS.2024.3},
  annote =	{Keywords: Structural graph theory, Monadic dependence, monadic NIP, twin-width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.4
Max Weight Independent Set in Sparse Graphs with No Long Claws

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski

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

Abstract
We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.
Cite as

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski. Max Weight Independent Set in Sparse Graphs with No Long Claws. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrishami_et_al:LIPIcs.STACS.2024.4,
  author =	{Abrishami, Tara and Chudnovsky, Maria and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Max Weight Independent Set in Sparse Graphs with No Long Claws}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.4},
  URN =		{urn:nbn:de:0030-drops-197148},
  doi =		{10.4230/LIPIcs.STACS.2024.4},
  annote =	{Keywords: Max Weight Independent Set, subdivided claw, hereditary classes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.5
Satisfiability of Context-Free String Constraints with Subword-Ordering and Transducers

Authors: C. Aiswarya, Soumodev Mal, and Prakash Saivasan

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

Abstract
We study the satisfiability of string constraints where context-free membership constraints may be imposed on variables. Additionally a variable may be constrained to be a subword of a word obtained by shuffling variables and their transductions. The satisfiability problem is known to be undecidable even without rational transductions. It is known to be NExptime-complete without transductions, if the subword relations between variables do not have a cyclic dependency between them. We show that the satisfiability problem stays decidable in this fragment even when rational transductions are added. It is 2NExptime-complete with context-free membership, and NExptime-complete with only regular membership. For the lower bound we prove a technical lemma that is of independent interest: The length of the shortest word in the intersection of a pushdown automaton (of size 𝒪(n)) and n finite-state automata (each of size 𝒪(n)) can be double exponential in n.
Cite as

C. Aiswarya, Soumodev Mal, and Prakash Saivasan. Satisfiability of Context-Free String Constraints with Subword-Ordering and Transducers. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aiswarya_et_al:LIPIcs.STACS.2024.5,
  author =	{Aiswarya, C. and Mal, Soumodev and Saivasan, Prakash},
  title =	{{Satisfiability of Context-Free String Constraints with Subword-Ordering and Transducers}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.5},
  URN =		{urn:nbn:de:0030-drops-197154},
  doi =		{10.4230/LIPIcs.STACS.2024.5},
  annote =	{Keywords: satisfiability, subword, string constraints, context-free, transducers}
}
  • Refine by Author
  • 78 Lokshtanov, Daniel
  • 58 Saurabh, Saket
  • 25 Zehavi, Meirav
  • 20 Fomin, Fedor V.
  • 16 Panolan, Fahad
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 15 parameterized complexity
  • 12 Parameterized Complexity
  • 9 treewidth
  • 8 kernelization
  • 6 FPT
  • Show More...

  • Refine by Type
  • 181 document
  • 2 volume

  • Refine by Publication Year
  • 69 2024
  • 43 2018
  • 12 2019
  • 12 2020
  • 8 2017
  • 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 About DROPS Imprint Privacy Contact