1763 Search Results for "Bend�k, J�n"

Document
DOI: 10.4230/LIPIcs.ICDT.2024.18
Computing Data Distribution from Query Selectivities

Authors: Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
We are given a set 𝒵 = {(R_1,s_1), …, (R_n,s_n)}, where each R_i is a range in ℝ^d, such as rectangle or ball, and s_i ∈ [0,1] denotes its selectivity. The goal is to compute a small-size discrete data distribution 𝒟 = {(q₁,w₁),…, (q_m,w_m)}, where q_j ∈ ℝ^d and w_j ∈ [0,1] for each 1 ≤ j ≤ m, and ∑_{1≤j≤m} w_j = 1, such that 𝒟 is the most consistent with 𝒵, i.e., err_p(𝒟,𝒵) = 1/n ∑_{i = 1}ⁿ |s_i - ∑_{j=1}^m w_j⋅1(q_j ∈ R_i)|^p is minimized. In a database setting, 𝒵 corresponds to a workload of range queries over some table, together with their observed selectivities (i.e., fraction of tuples returned), and 𝒟 can be used as compact model for approximating the data distribution within the table without accessing the underlying contents. In this paper, we obtain both upper and lower bounds for this problem. In particular, we show that the problem of finding the best data distribution from selectivity queries is NP-complete. On the positive side, we describe a Monte Carlo algorithm that constructs, in time O((n+δ^{-d}) δ^{-2} polylog n), a discrete distribution 𝒟̃ of size O(δ^{-2}), such that err_p(𝒟̃,𝒵) ≤ min_𝒟 err_p(𝒟,𝒵)+δ (for p = 1,2,∞) where the minimum is taken over all discrete distributions. We also establish conditional lower bounds, which strongly indicate the infeasibility of relative approximations as well as removal of the exponential dependency on the dimension for additive approximations. This suggests that significant improvements to our algorithm are unlikely.
Cite as

Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang. Computing Data Distribution from Query Selectivities. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICDT.2024.18,
  author =	{Agarwal, Pankaj K. and Raychaudhury, Rahul and Sintos, Stavros and Yang, Jun},
  title =	{{Computing Data Distribution from Query Selectivities}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.18},
  URN =		{urn:nbn:de:0030-drops-198007},
  doi =		{10.4230/LIPIcs.ICDT.2024.18},
  annote =	{Keywords: selectivity queries, discrete distributions, Multiplicative Weights Update, eps-approximation, learnable functions, depth problem, arrangement}
}
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.7
Computing Twin-Width Parameterized by the Feedback Edge Number

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

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

Abstract
The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an 𝓁-contraction sequence (for an arbitrary specified 𝓁) or determines that the twin-width of the input graph is at least 𝓁. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing Twin-Width Parameterized by the Feedback Edge Number. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.STACS.2024.7,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width Parameterized by the Feedback Edge Number}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.7},
  URN =		{urn:nbn:de:0030-drops-197170},
  doi =		{10.4230/LIPIcs.STACS.2024.7},
  annote =	{Keywords: twin-width, parameterized complexity, kernelization, feedback edge number}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.21
Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters

Authors: Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun

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

Abstract
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, n. In this paper, we focus on properties for which the size of the certificates does not depend on n but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: Θ(log k) for k-colorability (and even exactly ⌈ log k ⌉ bits in the anonymous model while previous works had only proved a 2-bit lower bound); (1/2)log t+o(log t) for dominating sets at distance t (an unexpected and tighter-than-usual bound) ; and Θ(log Δ) for perfect matching in graphs of maximum degree Δ (the first non-trivial bound parameterized by Δ). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2024.21,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Zeitoun, S\'{e}bastien},
  title =	{{Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{21:1--21:18},
  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.21},
  URN =		{urn:nbn:de:0030-drops-197317},
  doi =		{10.4230/LIPIcs.STACS.2024.21},
  annote =	{Keywords: Local certification, local properties, proof-labeling schemes, locally checkable proofs, optimal certification size, colorability, dominating set, perfect matching, fault-tolerance, graph structure}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.23
Fault-tolerant k-Supplier with Outliers

Authors: Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar

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

Abstract
We present approximation algorithms for the Fault-tolerant k-Supplier with Outliers (FkSO) problem. This is a common generalization of two known problems - k-Supplier with Outliers, and Fault-tolerant k-Supplier - each of which generalize the well-known k-Supplier problem. In the k-Supplier problem the goal is to serve n clients C, by opening k facilities from a set of possible facilities F; the objective function is the farthest that any client must travel to access an open facility. In FkSO, each client v has a fault-tolerance 𝓁_v, and now desires 𝓁_v facilities to serve it; so each client v’s contribution to the objective function is now its distance to the 𝓁_v^th closest open facility. Furthermore, we are allowed to choose m clients that we will serve, and only those clients contribute to the objective function, while the remaining n-m are considered outliers. Our main result is a (4t-1)-approximation for the FkSO problem, where t is the number of distinct values of 𝓁_v that appear in the instance. At t = 1, i.e. in the case where the 𝓁_v’s are uniformly some 𝓁, this yields a 3-approximation, improving upon the 11-approximation given for the uniform case by Inamdar and Varadarajan [2020], who also introduced the problem. Our result for the uniform case matches tight 3-approximations that exist for k-Supplier, k-Supplier with Outliers, and Fault-tolerant k-Supplier. Our key technical contribution is an application of the round-or-cut schema to FkSO. Guided by an LP relaxation, we reduce to a simpler optimization problem, which we can solve to obtain distance bounds for the "round" step, and valid inequalities for the "cut" step. By varying how we reduce to the simpler problem, we get varying distance bounds - we include a variant that gives a (2^t + 1)-approximation, which is better for t ∈ {2,3}. In addition, for t = 1, we give a more straightforward application of round-or-cut, yielding a 3-approximation that is much simpler than our general algorithm.
Cite as

Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar. Fault-tolerant k-Supplier with Outliers. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.STACS.2024.23,
  author =	{Chakrabarty, Deeparnab and Cote, Luc and Sarkar, Ankita},
  title =	{{Fault-tolerant k-Supplier with Outliers}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.23},
  URN =		{urn:nbn:de:0030-drops-197336},
  doi =		{10.4230/LIPIcs.STACS.2024.23},
  annote =	{Keywords: Clustering, approximation algorithms, round-or-cut}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.24
Approximate Circular Pattern Matching Under Edit Distance

Authors: Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba

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

Abstract
In the k-Edit Circular Pattern Matching (k-Edit CPM) problem, we are given a length-n text T, a length-m pattern P, and a positive integer threshold k, and we are to report all starting positions of the substrings of T that are at edit distance at most k from some cyclic rotation of P. In the decision version of the problem, we are to check if any such substring exists. Very recently, Charalampopoulos et al. [ESA 2022] presented 𝒪(nk²)-time and 𝒪(nk log³ k)-time solutions for the reporting and decision versions of k-Edit CPM, respectively. Here, we show that the reporting and decision versions of k-Edit CPM can be solved in 𝒪(n+(n/m) k⁶) time and 𝒪(n+(n/m) k⁵ log³ k) time, respectively, thus obtaining the first algorithms with a complexity of the type 𝒪(n+(n/m) poly(k)) for this problem. Notably, our algorithms run in 𝒪(n) time when m = Ω(k⁶) and are superior to the previous respective solutions when m = ω(k⁴). We provide a meta-algorithm that yields efficient algorithms in several other interesting settings, such as when the strings are given in a compressed form (as straight-line programs), when the strings are dynamic, or when we have a quantum computer. We obtain our solutions by exploiting the structure of approximate circular occurrences of P in T, when T is relatively short w.r.t. P. Roughly speaking, either the starting positions of approximate occurrences of rotations of P form 𝒪(k⁴) intervals that can be computed efficiently, or some rotation of P is almost periodic (is at a small edit distance from a string with small period). Dealing with the almost periodic case is the most technically demanding part of this work; we tackle it using properties of locked fragments (originating from [Cole and Hariharan, SICOMP 2002]).
Cite as

Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Approximate Circular Pattern Matching Under Edit Distance. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.STACS.2024.24,
  author =	{Charalampopoulos, Panagiotis and Pissis, Solon P. and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor},
  title =	{{Approximate Circular Pattern Matching Under Edit Distance}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{24:1--24:22},
  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.24},
  URN =		{urn:nbn:de:0030-drops-197346},
  doi =		{10.4230/LIPIcs.STACS.2024.24},
  annote =	{Keywords: circular pattern matching, approximate pattern matching, edit distance}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.25
Depth-3 Circuit Lower Bounds for k-OV

Authors: Tameem Choudhury and Karteek Sreenivasaiah

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

Abstract
The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples A and B of n Boolean vectors, each of dimension d, decide if there exist vectors u ∈ A, and v ∈ B, such that u and v are orthogonal. This problem, and its generalization k-OV defined analogously for k tuples, are central problems in the area of fine-grained complexity. One of the major conjectures in fine-grained complexity is that k-OV cannot be solved by a randomised algorithm in n^{k-ε}poly(d) time for any constant ε > 0. In this paper, we are interested in unconditional lower bounds against k-OV, but for weaker models of computation than the general Turing Machine. In particular, we are interested in circuit lower bounds to computing k-OV by Boolean circuit families of depth 3 of the form OR-AND-OR, or equivalently, a disjunction of CNFs. We show that for all k ≤ d, any disjunction of t-CNFs computing k-OV requires size Ω((n/t)^k). In particular, when k is a constant, any disjunction of k-CNFs computing k-OV needs to use Ω(n^k) CNFs. This matches the brute-force construction, and for each fixed k > 2, this is the first unconditional Ω(n^k) lower bound against k-OV for a computation model that can compute it in size O(n^k). Our results partially resolve a conjecture by Kane and Williams [Daniel M. Kane and Richard Ryan Williams, 2019] (page 12, conjecture 10) about depth-3 AC⁰ circuits computing 2-OV. As a secondary result, we show an exponential lower bound on the size of AND∘OR∘AND circuits computing 2-OV when d is very large. Since 2-OV reduces to k-OV by projections trivially, this lower bound works against k-OV as well.
Cite as

Tameem Choudhury and Karteek Sreenivasaiah. Depth-3 Circuit Lower Bounds for k-OV. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{choudhury_et_al:LIPIcs.STACS.2024.25,
  author =	{Choudhury, Tameem and Sreenivasaiah, Karteek},
  title =	{{Depth-3 Circuit Lower Bounds for k-OV}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-197359},
  doi =		{10.4230/LIPIcs.STACS.2024.25},
  annote =	{Keywords: fine grained complexity, k-OV, circuit lower bounds, depth-3 circuits}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.33
On the Exact Matching Problem in Dense Graphs

Authors: Nicolas El Maalouly, Sebastian Haslebacher, and Lasse Wulf

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

Abstract
In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly k red edges. Since 1987 it is known that the Exact Matching Problem can be solved in randomized polynomial time. Despite numerous efforts, it is still not known today whether a deterministic polynomial-time algorithm exists as well. In this paper, we make substantial progress by solving the problem for a multitude of different classes of dense graphs. We solve the Exact Matching problem in deterministic polynomial time for complete r-partite graphs, for unit interval graphs, for bipartite unit interval graphs, for graphs of bounded neighborhood diversity, for chain graphs, and for graphs without a complete bipartite t-hole. We solve the problem in quasi-polynomial time for Erdős-Rényi random graphs G(n, 1/2). We also reprove an earlier result for bounded independence number/bipartite independence number. We use two main tools to obtain these results: A local search algorithm as well as a generalization of an earlier result by Karzanov.
Cite as

Nicolas El Maalouly, Sebastian Haslebacher, and Lasse Wulf. On the Exact Matching Problem in Dense Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{elmaalouly_et_al:LIPIcs.STACS.2024.33,
  author =	{El Maalouly, Nicolas and Haslebacher, Sebastian and Wulf, Lasse},
  title =	{{On the Exact Matching Problem in Dense Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{33:1--33:17},
  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.33},
  URN =		{urn:nbn:de:0030-drops-197437},
  doi =		{10.4230/LIPIcs.STACS.2024.33},
  annote =	{Keywords: Exact Matching, Perfect Matching, Red-Blue Matching, Bounded Color Matching, Local Search, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.35
The 2-Attractor Problem Is NP-Complete

Authors: Janosch Fuchs and Philip Whittington

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

Abstract
A k-attractor is a combinatorial object unifying dictionary-based compression. It allows to compare the repetitiveness measures of different dictionary compressors such as Lempel-Ziv 77, the Burrows-Wheeler transform, straight line programs and macro schemes. For a string T ∈ Σⁿ, the k-attractor is defined as a set of positions Γ ⊆ [1,n], such that every distinct substring of length at most k is covered by at least one of the selected positions. Thus, if a substring occurs multiple times in T, one position suffices to cover it. A 1-attractor is easily computed in linear time, while Kempa and Prezza [STOC 2018] have shown that for k ≥ 3, it is NP-complete to compute the smallest k-attractor by a reduction from k-set cover. The main result of this paper answers the open question for the complexity of the 2-attractor problem, showing that the problem remains NP-complete. Kempa and Prezza’s proof for k ≥ 3 also reduces the 2-attractor problem to the 2-set cover problem, which is equivalent to edge cover, but that does not fully capture the complexity of the 2-attractor problem. For this reason, we extend edge cover by a color function on the edges, yielding the colorful edge cover problem. Any edge cover must then satisfy the additional constraint that each color is represented. This extension raises the complexity such that colorful edge cover becomes NP-complete while also more precisely modeling the 2-attractor problem. We obtain a reduction showing k-attractor to be NP-complete and APX-hard for any k ≥ 2.
Cite as

Janosch Fuchs and Philip Whittington. The 2-Attractor Problem Is NP-Complete. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.STACS.2024.35,
  author =	{Fuchs, Janosch and Whittington, Philip},
  title =	{{The 2-Attractor Problem Is NP-Complete}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{35:1--35:13},
  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.35},
  URN =		{urn:nbn:de:0030-drops-197457},
  doi =		{10.4230/LIPIcs.STACS.2024.35},
  annote =	{Keywords: String attractors, dictionary compression, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.40
A Faster Algorithm for Vertex Cover Parameterized by Solution Size

Authors: David G. Harris and N. S. Narayanaswamy

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

Abstract
We describe a new algorithm for vertex cover with runtime O^*(1.25284^k), where k is the size of the desired solution and O^* hides polynomial factors in the input size. This improves over the previous runtime of O^*(1.2738^k) due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a measure which simultaneously tracks k as well as the optimal value λ of the vertex cover LP relaxation. This allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both k and μ = k - λ are decreased at each step. There can be local obstructions in the graph that prevent μ from decreasing in this process; we develop a number of novel branching steps to handle these situations.
Cite as

David G. Harris and N. S. Narayanaswamy. A Faster Algorithm for Vertex Cover Parameterized by Solution Size. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.STACS.2024.40,
  author =	{Harris, David G. and Narayanaswamy, N. S.},
  title =	{{A Faster Algorithm for Vertex Cover Parameterized by Solution Size}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{40:1--40:18},
  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.40},
  URN =		{urn:nbn:de:0030-drops-197508},
  doi =		{10.4230/LIPIcs.STACS.2024.40},
  annote =	{Keywords: Vertex cover, FPT, Graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.43
A Faster Algorithm for Constructing the Frequency Difference Consensus Tree

Authors: Jesper Jansson, Wing-Kin Sung, Seyed Ali Tabatabaee, and Yutong Yang

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

Abstract
A consensus tree is a phylogenetic tree that summarizes the evolutionary relationships inferred from a collection of phylogenetic trees with the same set of leaf labels. Among the many types of consensus trees that have been proposed in the last 50 years, the frequency difference consensus tree is one of the more finely resolved types that retains a large amount of information. This paper presents a new deterministic algorithm for constructing the frequency difference consensus tree. Given k phylogenetic trees with identical sets of n leaf labels, it runs in O(knlog{n}) time, improving the best previously known solution.
Cite as

Jesper Jansson, Wing-Kin Sung, Seyed Ali Tabatabaee, and Yutong Yang. A Faster Algorithm for Constructing the Frequency Difference Consensus Tree. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jansson_et_al:LIPIcs.STACS.2024.43,
  author =	{Jansson, Jesper and Sung, Wing-Kin and Tabatabaee, Seyed Ali and Yang, Yutong},
  title =	{{A Faster Algorithm for Constructing the Frequency Difference Consensus Tree}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{43:1--43:17},
  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.43},
  URN =		{urn:nbn:de:0030-drops-197539},
  doi =		{10.4230/LIPIcs.STACS.2024.43},
  annote =	{Keywords: phylogenetic tree, frequency difference consensus tree, tree algorithm, centroid path decomposition, max-Manhattan Skyline Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.44
Decremental Sensitivity Oracles for Covering and Packing Minors

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

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

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

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

Copy BibTex To Clipboard

@InProceedings{kanesh_et_al:LIPIcs.STACS.2024.44,
  author =	{Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Strulo, Peter},
  title =	{{Decremental Sensitivity Oracles for Covering and Packing Minors}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.44},
  URN =		{urn:nbn:de:0030-drops-197544},
  doi =		{10.4230/LIPIcs.STACS.2024.44},
  annote =	{Keywords: Sensitivity oracles, Data Structures, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.47
Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane

Authors: Katarzyna Kowalska and Michał Pilipczuk

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

Abstract
We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segment Set Cover. We also consider a relaxation of the problem called δ-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution’s quality to the optimum without extension. For the unparameterized variant, we prove that Segment Set Cover does not admit a PTAS unless P=NP, even if we restrict segments to be axis-parallel and allow 1/2-extension. On the other hand, we show that parameterization helps for the tractability of Segment Set Cover: we give an FPT algorithm for unweighted Segment Set Cover parameterized by the solution size k, a parameterized approximation scheme for Weighted Segment Set Cover with k being the parameter, and an FPT algorithm for Weighted Segment Set Cover with δ-extension parameterized by k and δ. In the last two results, relaxing the problem is probably necessary: we prove that Weighted Segment Set Cover without any relaxation is W[1]-hard and, assuming ETH, there does not exist an algorithm running in time f(k)⋅ n^{o(k / log k)}. This holds even if one restricts attention to axis-parallel segments.
Cite as

Katarzyna Kowalska and Michał Pilipczuk. Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kowalska_et_al:LIPIcs.STACS.2024.47,
  author =	{Kowalska, Katarzyna and Pilipczuk, Micha{\l}},
  title =	{{Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{47:1--47:16},
  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.47},
  URN =		{urn:nbn:de:0030-drops-197572},
  doi =		{10.4230/LIPIcs.STACS.2024.47},
  annote =	{Keywords: Geometric Set Cover, fixed-parameter tractability, weighted parameterized problems, parameterized approximation scheme}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.52
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering

Authors: Bodo Manthey and Jesse van Rhijn

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

Abstract
We analyze the running time of the Hartigan-Wong method, an old algorithm for the k-means clustering problem. First, we construct an instance on the line on which the method can take 2^{Ω(n)} steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when k-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of n points in d dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by k^{12kd}⋅ poly(n, k, d, 1/σ) when the points in the instance are perturbed by independent d-dimensional Gaussian random variables of mean 0 and standard deviation σ.
Cite as

Bodo Manthey and Jesse van Rhijn. Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{manthey_et_al:LIPIcs.STACS.2024.52,
  author =	{Manthey, Bodo and van Rhijn, Jesse},
  title =	{{Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{52:1--52:16},
  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.52},
  URN =		{urn:nbn:de:0030-drops-197628},
  doi =		{10.4230/LIPIcs.STACS.2024.52},
  annote =	{Keywords: k-means clustering, smoothed analysis, probabilistic analysis, local search, heuristics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.53
Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width

Authors: Daniel Neuen

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

Abstract
Two graphs are homomorphism indistinguishable over a graph class 𝐅, denoted by G ≡_𝐅 H, if hom(F,G) = hom(F,H) for all F ∈ 𝐅 where hom(F,G) denotes the number of homomorphisms from F to G. A classical result of Lovász shows that isomorphism between graphs is equivalent to homomorphism indistinguishability over the class of all graphs. More recently, there has been a series of works giving natural algebraic and/or logical characterizations for homomorphism indistinguishability over certain restricted graph classes. A class of graphs 𝐅 is homomorphism-distinguishing closed if, for every F ∉ 𝐅, there are graphs G and H such that G ≡_𝐅 H and hom(F,G) ≠ hom(F,H). Roberson conjectured that every class closed under taking minors and disjoint unions is homomorphism-distinguishing closed which implies that every such class defines a distinct equivalence relation between graphs. In this work, we confirm this conjecture for the classes 𝒯_k, k ≥ 1, containing all graphs of tree-width at most k. As an application of this result, we also characterize which subgraph counts are detected by the k-dimensional Weisfeiler-Leman algorithm. This answers an open question from [Arvind et al., J. Comput. Syst. Sci., 2020].
Cite as

Daniel Neuen. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{neuen:LIPIcs.STACS.2024.53,
  author =	{Neuen, Daniel},
  title =	{{Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{53:1--53:12},
  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.53},
  URN =		{urn:nbn:de:0030-drops-197630},
  doi =		{10.4230/LIPIcs.STACS.2024.53},
  annote =	{Keywords: homomorphism indistinguishability, tree-width, Weisfeiler-Leman algorithm, subgraph counts}
}
  • Refine by Author
  • 58 Saurabh, Saket
  • 35 Fomin, Fedor V.
  • 35 Lokshtanov, Daniel
  • 23 Panolan, Fahad
  • 21 Agarwal, Pankaj K.
  • Show More...

  • Refine by Classification
  • 132 Theory of computation → Design and analysis of algorithms
  • 131 Theory of computation → Computational geometry
  • 113 Theory of computation → Parameterized complexity and exact algorithms
  • 89 Theory of computation → Graph algorithms analysis
  • 78 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 55 parameterized complexity
  • 49 approximation algorithms
  • 34 lower bounds
  • 32 Approximation Algorithms
  • 32 fixed-parameter tractability
  • Show More...

  • Refine by Type
  • 1763 document

  • Refine by Publication Year
  • 229 2022
  • 212 2023
  • 208 2020
  • 182 2019
  • 178 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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