DROPS

Volume

OASIcs, Volume 7

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)

ATMOS 2007, November 15-16, 2007, Sevilla, Spain

Editors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Document

DOI: 10.4230/LIPIcs.STACS.2024.12

Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form

Authors: Christoph Berkholz, Dietrich Kuske, and Christian Schwarz

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

Abstract

Is it possible to write significantly smaller formulae, when using more Boolean operators in addition to the De Morgan basis (and, or, not)? For propositional logic a negative answer was given by Pratt: every formula with additional operators can be translated to the De Morgan basis with only polynomial increase in size. Surprisingly, for modal logic the picture is different: we show that adding bi-implication allows to write exponentially smaller formulae. Moreover, we provide a complete classification of finite sets of Boolean operators showing they are either of no help (allow polynomial translations to the De Morgan basis) or can express properties as succinct as modal logic with additional bi-implication. More precisely, these results are shown for the modal logic T (and therefore for K). We complement this result showing that the modal logic S5 behaves as propositional logic: no additional Boolean operators make it possible to write significantly smaller formulae.

Cite as

Christoph Berkholz, Dietrich Kuske, and Christian Schwarz. Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.STACS.2024.12,
  author =	{Berkholz, Christoph and Kuske, Dietrich and Schwarz, Christian},
  title =	{{Modal Logic Is More Succinct Iff Bi-Implication Is Available in Some Form}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-197228},
  doi =		{10.4230/LIPIcs.STACS.2024.12},
  annote =	{Keywords: succinctness, modal logic}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2023.54

On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric

Authors: Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, and Bernhard Seeger

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We initiate a study of the complexity of MSM-Median, the problem of computing a median of a set of k real-valued time series under the move-split-merge distance. This distance measure is based on three operations: moves, which may shift a data point in a time series; splits, which replace one data point in a time series by two consecutive data points of the same value; and merges, which replace two consecutive data points of equal value by a single data point of the same value. The cost of a move operation is the difference of the data point value before and after the operation, the cost of split and merge operations is defined via a given constant c. Our main results are as follows. First, we show that MSM-Median is NP-hard and W[1]-hard with respect to k for time series with at most three distinct values. Under the Exponential Time Hypothesis (ETH) our reduction implies that a previous dynamic programming algorithm with running time |I|^𝒪(k) [Holznigenkemper et al., Data Min. Knowl. Discov. '23] is essentially optimal. Here, |I| denotes the total input size. Second, we show that MSM-Median can be solved in 2^𝒪(d/c)⋅|I|^𝒪(1) time where d is the total distance of the median to the input time series.

Cite as

Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, and Bernhard Seeger. On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{holznigenkemper_et_al:LIPIcs.MFCS.2023.54,
  author =	{Holznigenkemper, Jana and Komusiewicz, Christian and Morawietz, Nils and Seeger, Bernhard},
  title =	{{On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{54:1--54: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.54},
  URN =		{urn:nbn:de:0030-drops-185889},
  doi =		{10.4230/LIPIcs.MFCS.2023.54},
  annote =	{Keywords: Parameterized Complexity, Median String, Time Series, ETH}
}

Document

DOI: 10.4230/LIPIcs.SEA.2023.15

FREIGHT: Fast Streaming Hypergraph Partitioning

Authors: Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract

Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

Cite as

Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz. FREIGHT: Fast Streaming Hypergraph Partitioning. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eyubov_et_al:LIPIcs.SEA.2023.15,
  author =	{Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15},
  URN =		{urn:nbn:de:0030-drops-183657},
  doi =		{10.4230/LIPIcs.SEA.2023.15},
  annote =	{Keywords: Hypergraph partitioning, graph partitioning, edge partitioning, streaming}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.50

Connected k-Center and k-Diameter Clustering

Authors: Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt, and Julian Wargalla

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an O(1)-approximation algorithm for the disjoint connected k-center and k-diameter problem for Euclidean spaces of low dimension (constant d) and for metrics with constant doubling dimension. For general metrics, we get an O(log²k)-approximation. Our algorithms work by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model.

Cite as

Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt, and Julian Wargalla. Connected k-Center and k-Diameter Clustering. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{drexler_et_al:LIPIcs.ICALP.2023.50,
  author =	{Drexler, Lukas and Eube, Jan and Luo, Kelin and R\"{o}glin, Heiko and Schmidt, Melanie and Wargalla, Julian},
  title =	{{Connected k-Center and k-Diameter Clustering}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{50:1--50:20},
  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.50},
  URN =		{urn:nbn:de:0030-drops-181024},
  doi =		{10.4230/LIPIcs.ICALP.2023.50},
  annote =	{Keywords: Approximation algorithms, Clustering, Connectivity constraints}
}

Document

DOI: 10.4230/LIPIcs.CPM.2023.18

On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem

Authors: Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract

Maximum Parsimony is the problem of computing a most parsimonious phylogenetic tree for a taxa set X from character data for X. A common strategy to attack this notoriously hard problem is to perform a local search over the phylogenetic tree space. Here, one is given a phylogenetic tree T and wants to find a more parsimonious tree in the neighborhood of T. We study the complexity of this problem when the neighborhood contains all trees within distance k for several classic distance functions. For the nearest neighbor interchange (NNI), subtree prune and regraft (SPR), tree bisection and reconnection (TBR), and edge contraction and refinement (ECR) distances, we show that, under the exponential time hypothesis, there are no algorithms with running time |I|^o(k) where |I| is the total input size. Hence, brute-force algorithms with running time |X|^𝒪(k) ⋅ |I| are essentially optimal. In contrast to the above distances, we observe that for the sECR-distance, where the contracted edges are constrained to form a subtree, a better solution within distance k can be found in k^𝒪(k) ⋅ |I|^𝒪(1) time.

Cite as

Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18,
  author =	{Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik},
  title =	{{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.18},
  URN =		{urn:nbn:de:0030-drops-179729},
  doi =		{10.4230/LIPIcs.CPM.2023.18},
  annote =	{Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2023.5

An Optimal Algorithm for Sliding Window Order Statistics

Authors: Pavel Raykov

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract

Assume there is a data stream of elements and a window of size m. Sliding window algorithms compute various statistic functions over the last m elements of the data stream seen so far. The time complexity of a sliding window algorithm is measured as the time required to output an updated statistic function value every time a new element is read. For example, it is well known that computing the sliding window maximum/minimum has time complexity O(1) while computing the sliding window median has time complexity O(log m). In this paper we close the gap between these two cases by (1) presenting an algorithm for computing the sliding window k-th smallest element in O(log k) time and (2) prove that this time complexity is optimal.

Cite as

Pavel Raykov. An Optimal Algorithm for Sliding Window Order Statistics. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{raykov:LIPIcs.ICDT.2023.5,
  author =	{Raykov, Pavel},
  title =	{{An Optimal Algorithm for Sliding Window Order Statistics}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5},
  URN =		{urn:nbn:de:0030-drops-177479},
  doi =		{10.4230/LIPIcs.ICDT.2023.5},
  annote =	{Keywords: sliding window, order statistics, median, selection algorithms}
}

Document

DOI: 10.4230/LIPIcs.STACS.2023.6

Improved Weighted Matching in the Sliding Window Model

Authors: Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a given vertex set V of size n. The objective is to maintain an approximation of a maximum-weight matching in the graph spanned by the L most recent edges, for some integer L, using as little space as possible. Prior to our work, the state-of-the-art results were a (3.5+ε)-approximation algorithm for MWM by Biabani et al. [ISAAC'21] and a (3+ε)-approximation for (unweighted) Maximum Matching (MM) by Crouch et al. [ESA'13]. Both algorithms use space Õ(n). We give the following results: 1) We give a (2+ε)-approximation algorithm for MWM with space Õ(√{nL}). Under the reasonable assumption that the graphs spanned by the edges in each sliding window are simple, our algorithm uses space Õ(n √n). 2) In the Õ(n) space regime, we give a (3+ε)-approximation algorithm for MWM, thereby closing the gap between the best-known approximation ratio for MWM and MM. Similar to Biabani et al.’s MWM algorithm, both our algorithms execute multiple instances of the (2+ε)-approximation Õ(n)-space streaming algorithm for MWM by Paz and Schwartzman [SODA'17] on different portions of the stream. Our improvements are obtained by selecting these substreams differently. Furthermore, our (2+ε)-approximation algorithm runs the Paz-Schwartzman algorithm in reverse direction over some parts of the stream, and in forward direction over other parts, which allows for an improved approximation guarantee at the cost of increased space requirements.

Cite as

Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu. Improved Weighted Matching in the Sliding Window Model. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alexandru_et_al:LIPIcs.STACS.2023.6,
  author =	{Alexandru, Cezar-Mihail and Dvo\v{r}\'{a}k, Pavel and Konrad, Christian and Naidu, Kheeran K.},
  title =	{{Improved Weighted Matching in the Sliding Window Model}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.6},
  URN =		{urn:nbn:de:0030-drops-176585},
  doi =		{10.4230/LIPIcs.STACS.2023.6},
  annote =	{Keywords: Sliding window algorithms, Streaming algorithms, Maximum-weight matching}
}

Document

DOI: 10.4230/LIPIcs.STACS.2023.41

Maximum Matching via Maximal Matching Queries

Authors: Christian Konrad, Kheeran K. Naidu, and Arun Steward

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

We study approximation algorithms for Maximum Matching that are given access to the input graph solely via an edge-query maximal matching oracle. More specifically, in each round, an algorithm queries a set of potential edges and the oracle returns a maximal matching in the subgraph spanned by the query edges that are also contained in the input graph. This model is more general than the vertex-query model introduced by binti Khalil and Konrad [FSTTCS'20], where each query consists of a subset of vertices and the oracle returns a maximal matching in the subgraph of the input graph induced by the queried vertices. In this paper, we give tight bounds for deterministic edge-query algorithms for up to three rounds. In more detail: 1) As our main result, we give a deterministic 3-round edge-query algorithm with approximation factor 0.625 on bipartite graphs. This result establishes a separation between the edge-query and the vertex-query models since every deterministic 3-round vertex-query algorithm has an approximation factor of at most 0.6 [binti Khalil, Konrad, FSTTCS'20], even on bipartite graphs. Our algorithm can also be implemented in the semi-streaming model of computation in a straightforward manner and improves upon the state-of-the-art 3-pass 0.6111-approximation algorithm by Feldman and Szarf [APPROX'22] for bipartite graphs. 2) We show that the aforementioned algorithm is optimal in that every deterministic 3-round edge-query algorithm has an approximation factor of at most 0.625, even on bipartite graphs. 3) Last, we also give optimal bounds for one and two query rounds, where the best approximation factors achievable are 1/2 and 1/2 + Θ(1/n), respectively, where n is the number of vertices in the input graph.

Cite as

Christian Konrad, Kheeran K. Naidu, and Arun Steward. Maximum Matching via Maximal Matching Queries. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.STACS.2023.41,
  author =	{Konrad, Christian and Naidu, Kheeran K. and Steward, Arun},
  title =	{{Maximum Matching via Maximal Matching Queries}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.41},
  URN =		{urn:nbn:de:0030-drops-176935},
  doi =		{10.4230/LIPIcs.STACS.2023.41},
  annote =	{Keywords: Maximum Matching, Query Model, Algorithms, Lower Bounds}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2022.20

Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial

Authors: Christian Komusiewicz and Nils Morawietz

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

Abstract

A k-swap W for a vertex cover S of a graph G is a vertex set of size at most k such that S' = (S ⧵ W) ∪ (W ⧵ S), the symmetric difference of S and W, is a vertex cover of G. If |S'| < |S|, then W is improving. In LS-Vertex Cover, one is given a vertex cover S of a graph G and wants to know if there is an improving k-swap for S in G. In applications of LS-Vertex Cover, k is a very small parameter that can be set by a user to determine the trade-off between running time and solution quality. Consequently, k can be considered to be a constant. Motivated by this and the fact that LS-Vertex Cover is W[1]-hard with respect to k, we aim for algorithms with running time 𝓁^f(k) ⋅ n^𝒪(1) where 𝓁 is a structural graph parameter upper-bounded by n. We say that such a running time grows mildly with respect to 𝓁 and strongly with respect to k. We obtain algorithms with such a running time for 𝓁 being the h-index of G, the treewidth of G, or the modular-width of G. In addition, we consider a novel parameter, the maximum degree over all quotient graphs in a modular decomposition of G. Moreover, we adapt these algorithms to the more general problem where each vertex is assigned a weight and where we want to find a d-improving k-swap, that is, a k-swap which decreases the weight of the vertex cover by at least d.

Cite as

Christian Komusiewicz and Nils Morawietz. Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2022.20,
  author =	{Komusiewicz, Christian and Morawietz, Nils},
  title =	{{Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.20},
  URN =		{urn:nbn:de:0030-drops-173764},
  doi =		{10.4230/LIPIcs.IPEC.2022.20},
  annote =	{Keywords: Local Search, Structural parameterization, Fixed-parameter tractability}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.8

Efficient Classification of Locally Checkable Problems in Regular Trees

Authors: Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the [Θ(log n), Θ(n)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k. In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.

Cite as

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8,
  author =	{Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Efficient Classification of Locally Checkable Problems in Regular Trees}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.8},
  URN =		{urn:nbn:de:0030-drops-171993},
  doi =		{10.4230/LIPIcs.DISC.2022.8},
  annote =	{Keywords: locally checkable labeling, locality, distributed computational complexity}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.17

Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy

Authors: Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω(1/polylog(k)) and energy O((log² k)/(log log k)²).

Cite as

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.DISC.2022.17,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
  title =	{{Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.17},
  URN =		{urn:nbn:de:0030-drops-172081},
  doi =		{10.4230/LIPIcs.DISC.2022.17},
  annote =	{Keywords: Shared channel, Contention resolution, Throughput, Energy consumption, Randomized algorithms, Lower bound}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.18

Smoothed Analysis of Information Spreading in Dynamic Networks

Authors: Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

The best known solutions for k-message broadcast in dynamic networks of size n require Ω(nk) rounds. In this paper, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k-message broadcast in Õ(n+k³) rounds, with high probability, beating the best known bounds for k = o(√n) and matching the Ω(n+k) lower bound for static networks for k = O(n^{1/3}) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given 𝓁-smoothing (i.e., 𝓁 random edges added per round), this simple strategy terminates in O(kn^{2/3}log^{1/3}(n)𝓁^{-1/3}) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of Õ(k√n) rounds to solve k-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k-message broadcast problem.

Cite as

Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport. Smoothed Analysis of Information Spreading in Dynamic Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.DISC.2022.18,
  author =	{Dinitz, Michael and Fineman, Jeremy and Gilbert, Seth and Newport, Calvin},
  title =	{{Smoothed Analysis of Information Spreading in Dynamic Networks}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.18},
  URN =		{urn:nbn:de:0030-drops-172094},
  doi =		{10.4230/LIPIcs.DISC.2022.18},
  annote =	{Keywords: Smoothed Analysis, Dynamic networks, Gossip}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.19

An Almost Singularly Optimal Asynchronous Distributed MST Algorithm

Authors: Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks. In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D^{1+ε} + √n) time and Õ(m) messages, where n is the number of nodes, m the number of edges, D is the diameter of the network, and ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since Ω̃(D+√n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT₀ model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a D^ε factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n^{1-ε})) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT₁ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D^{1+ε}) (for an arbitrarily small constant ε > 0) in Õ(D^{1+ε}) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently performing basic tasks such as verified broadcast and convergecast in asynchronous networks.

Cite as

Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19,
  author =	{Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.19},
  URN =		{urn:nbn:de:0030-drops-172107},
  doi =		{10.4230/LIPIcs.DISC.2022.19},
  annote =	{Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.26

Fast Distributed Vertex Splitting with Applications

Authors: Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

Cite as

Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2022.26,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Maus, Yannic and Nolin, Alexandre},
  title =	{{Fast Distributed Vertex Splitting with Applications}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{26:1--26:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.26},
  URN =		{urn:nbn:de:0030-drops-172176},
  doi =		{10.4230/LIPIcs.DISC.2022.26},
  annote =	{Keywords: Graph problems, Edge coloring, List coloring, Lov\'{a}sz local lemma, LOCAL model, CONGEST model, Distributed computing}
}

124 Search Results for "K�stner, Christian"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message