117 Search Results for "Papadimitriou, Christos H."

Volume

LIPIcs, Volume 67

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

ITCS 2017, January 9-11, 2017, Berkeley, CA, USA

Editors: Christos H. Papadimitriou

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.1
A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP

Authors: Susanne Armbruster, Matthias Mnich, and Martin Nägele

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

Abstract
We present a new (3/2 + 1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classic metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.
Cite as

Susanne Armbruster, Matthias Mnich, and Martin Nägele. A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{armbruster_et_al:LIPIcs.APPROX/RANDOM.2024.1,
  author =	{Armbruster, Susanne and Mnich, Matthias and N\"{a}gele, Martin},
  title =	{{A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{1:1--1:18},
  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.1},
  URN =		{urn:nbn:de:0030-drops-209943},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.1},
  annote =	{Keywords: Travelling Salesperson Problem, precedence constraints, linear programming, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.10
Optimal RANDAO Manipulation in Ethereum

Authors: Kaya Alpturer and S. Matthew Weinberg

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
It is well-known that RANDAO manipulation is possible in Ethereum if an adversary controls the proposers assigned to the last slots in an epoch. We provide a methodology to compute, for any fraction α of stake owned by an adversary, the maximum fraction f(α) of rounds that a strategic adversary can propose. We further implement our methodology and compute f(⋅) for all α. For example, we conclude that an optimal strategic participant with 5% of the stake can propose a 5.048% fraction of rounds, 10% of the stake can propose a 10.19% fraction of rounds, and 20% of the stake can propose a 20.68% fraction of rounds.
Cite as

Kaya Alpturer and S. Matthew Weinberg. Optimal RANDAO Manipulation in Ethereum. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpturer_et_al:LIPIcs.AFT.2024.10,
  author =	{Alpturer, Kaya and Weinberg, S. Matthew},
  title =	{{Optimal RANDAO Manipulation in Ethereum}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.10},
  URN =		{urn:nbn:de:0030-drops-209467},
  doi =		{10.4230/LIPIcs.AFT.2024.10},
  annote =	{Keywords: Proof of Stake, Consensus, Blockchain, Ethereum, Randomness manipulation}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.13
Musketeer: Incentive-Compatible Rebalancing for Payment Channel Networks

Authors: Zeta Avarikioti, Stefan Schmid, and Samarth Tiwari

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
In this work, we revisit the severely limited throughput problem of cryptocurrencies and propose a novel rebalancing approach for Payment Channel Networks (PCNs). PCNs are a popular solution for increasing the blockchain throughput, however, their benefit depends on the overall users' liquidity. Rebalancing mechanisms are the state-of-the-art approach to maintaining high liquidity in PCNs. However, existing opt-in rebalancing mechanisms exclude users that may assist in rebalancing for small service fees, leading to suboptimal solutions and under-utilization of the PCNs' bounded liquidity. We introduce the first rebalancing approach for PCNs that includes all users, following a "all for one and one for all" design philosophy that yields optimal throughput. The proposed approach introduces a double-auction rebalancing problem, which we term Musketeer, where users can participate as buyers (paying fees to rebalance) or sellers (charging fees to route transactions). The desired properties tailored to the unique characteristics of PCNs are formally defined, including the novel game-theoretic property of cyclic budget balance that is a stronger variation of strong budget balance. Basic results derived from auction theory, including an impossibility and multiple mechanisms that either achieve all desiderata under a relaxed model or sacrifice one of the properties, are presented. We also propose a novel mechanism that leverages time delays as an additional cost to users. This mechanism is provably truthful, cyclic budget balanced, individually rational and economic efficient but only with respect to liquidity.
Cite as

Zeta Avarikioti, Stefan Schmid, and Samarth Tiwari. Musketeer: Incentive-Compatible Rebalancing for Payment Channel Networks. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{avarikioti_et_al:LIPIcs.AFT.2024.13,
  author =	{Avarikioti, Zeta and Schmid, Stefan and Tiwari, Samarth},
  title =	{{Musketeer: Incentive-Compatible Rebalancing for Payment Channel Networks}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.13},
  URN =		{urn:nbn:de:0030-drops-209494},
  doi =		{10.4230/LIPIcs.AFT.2024.13},
  annote =	{Keywords: Blockchains, Payment Channel Networks, Rebalancing, Game Theory}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.30
Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable

Authors: Linda Cai, Jingyi Liu, S. Matthew Weinberg, and Chenghan Zhou

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
Cryptographic Self-Selection is a common primitive underlying leader-selection for Proof-of-Stake blockchain protocols. The concept was first popularized in Algorand [Jing Chen and Silvio Micali, 2019], who also observed that the protocol might be manipulable. [Matheus V. X. Ferreira et al., 2022] provide a concrete manipulation that is strictly profitable for a staker of any size (and also prove upper bounds on the gains from manipulation). Separately, [Maryam Bahrani and S. Matthew Weinberg, 2024; Aviv Yaish et al., 2023] initiate the study of undetectable profitable manipulations of consensus protocols with a focus on the seminal Selfish Mining strategy [Eyal and Sirer, 2014] for Bitcoin’s Proof-of-Work longest-chain protocol. They design a Selfish Mining variant that, for sufficiently large miners, is strictly profitable yet also indistinguishable to an onlooker from routine latency (that is, a sufficiently large profit-maximizing miner could use their strategy to strictly profit over being honest in a way that still appears to the rest of the network as though everyone is honest but experiencing mildly higher latency. This avoids any risk of negatively impacting the value of the underlying cryptocurrency due to attack detection). We investigate the detectability of profitable manipulations of the canonical cryptographic self-selection leader selection protocol introduced in [Jing Chen and Silvio Micali, 2019] and studied in [Matheus V. X. Ferreira et al., 2022], and establish that for any player with α < (3-√5)/2 ≈ 0.38 fraction of the total stake, every strictly profitable manipulation is statistically detectable. Specifically, we consider an onlooker who sees only the random seed of each round (and does not need to see any other broadcasts by any other players). We show that the distribution of the sequence of random seeds when any player is profitably manipulating the protocol is inconsistent with any distribution that could arise by honest stakers being offline or timing out (for a natural stylized model of honest timeouts).
Cite as

Linda Cai, Jingyi Liu, S. Matthew Weinberg, and Chenghan Zhou. Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AFT.2024.30,
  author =	{Cai, Linda and Liu, Jingyi and Weinberg, S. Matthew and Zhou, Chenghan},
  title =	{{Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.30},
  URN =		{urn:nbn:de:0030-drops-209660},
  doi =		{10.4230/LIPIcs.AFT.2024.30},
  annote =	{Keywords: Blockchain, Cryptocurrency, Proof-of-Stake, Strategic Mining, Statistical Detection}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.14
As Soon as Possible but Rationally

Authors: Véronique Bruyère, Christophe Grandmont, and Jean-François Raskin

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
This paper addresses complexity problems in rational verification and synthesis for multi-player games played on weighted graphs, where the objective of each player is to minimize the cost of reaching a specific set of target vertices. In these games, one player, referred to as the system, declares his strategy upfront. The other players, composing the environment, then rationally make their moves according to their objectives. The rational behavior of these responding players is captured through two models: they opt for strategies that either represent a Nash equilibrium or lead to a play with a Pareto-optimal cost tuple.
Cite as

Véronique Bruyère, Christophe Grandmont, and Jean-François Raskin. As Soon as Possible but Rationally. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bruyere_et_al:LIPIcs.CONCUR.2024.14,
  author =	{Bruy\`{e}re, V\'{e}ronique and Grandmont, Christophe and Raskin, Jean-Fran\c{c}ois},
  title =	{{As Soon as Possible but Rationally}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.14},
  URN =		{urn:nbn:de:0030-drops-207869},
  doi =		{10.4230/LIPIcs.CONCUR.2024.14},
  annote =	{Keywords: Games played on graphs, rational verification, rational synthesis, Nash equilibrium, Pareto-optimality, quantitative reachability objectives}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.40
A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs

Authors: Marnix Suilen, Marck van der Vegt, and Sebastian Junges

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
Markov Decision Processes (MDPs) model systems with uncertain transition dynamics. Multiple-environment MDPs (MEMDPs) extend MDPs. They intuitively reflect finite sets of MDPs that share the same state and action spaces but differ in the transition dynamics. The key objective in MEMDPs is to find a single strategy that satisfies a given objective in every associated MDP. The main result of this paper is PSPACE-completeness for almost-sure Rabin objectives in MEMDPs. This result clarifies the complexity landscape for MEMDPs and contrasts with results for the more general class of partially observable MDPs (POMDPs), where almost-sure reachability is already EXP-complete, and almost-sure Rabin objectives are undecidable.
Cite as

Marnix Suilen, Marck van der Vegt, and Sebastian Junges. A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{suilen_et_al:LIPIcs.CONCUR.2024.40,
  author =	{Suilen, Marnix and van der Vegt, Marck and Junges, Sebastian},
  title =	{{A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.40},
  URN =		{urn:nbn:de:0030-drops-208120},
  doi =		{10.4230/LIPIcs.CONCUR.2024.40},
  annote =	{Keywords: Markov Decision Processes, partial observability, linear-time Objectives}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.9
Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms

Authors: Emir Demirović, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, and Konstantin Sidorov

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Pseudo-Boolean proof logging has been used successfully to provide certificates of optimality from a variety of constraint- and satisifability-style solvers that combine reasoning with a backtracking or clause-learning search. Another paradigm, occurring in dynamic programming and decision diagram solving, instead reasons about partial states and possible transitions between them. We describe a framework for generating clean and efficient pseudo-Boolean proofs for these kinds of algorithm, and use it to produce certifying algorithms for knapsack, longest path, and interval scheduling. Because we use a common proof system, we can also reason about hybrid solving algorithms: we demonstrate this by providing proof logging for a dynamic programming based knapsack propagator inside a constraint programming solver.
Cite as

Emir Demirović, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, and Konstantin Sidorov. Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{demirovic_et_al:LIPIcs.CP.2024.9,
  author =	{Demirovi\'{c}, Emir and McCreesh, Ciaran and McIlree, Matthew J. and Nordstr\"{o}m, Jakob and Oertel, Andy and Sidorov, Konstantin},
  title =	{{Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.9},
  URN =		{urn:nbn:de:0030-drops-206948},
  doi =		{10.4230/LIPIcs.CP.2024.9},
  annote =	{Keywords: Proof logging, dynamic programming, decision diagrams}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.17
Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four

Authors: Artem Kaznatcheev and Melle van Marle

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
We examine the complexity of maximising fitness via local search on valued constraint satisfaction problems (VCSPs). We consider two kinds of local ascents: (1) steepest ascents, where each step changes the domain that produces a maximal increase in fitness; and (2) ≺-ordered ascents, where - of the domains with available fitness increasing changes - each step changes the ≺-minimal domain. We provide a general padding argument to simulate any ordered ascent by a steepest ascent. We construct a VCSP that is a path of binary constraints between alternating 2-state and 3-state domains with exponentially long ordered ascents. We apply our padding argument to this VCSP to obtain a Boolean VCSP that has a constraint (hyper)graph of arity 5 and pathwidth 4 with exponential steepest ascents. This is an improvement on the previous best known construction for long steepest ascents, which had arity 8 and pathwidth 7.
Cite as

Artem Kaznatcheev and Melle van Marle. Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kaznatcheev_et_al:LIPIcs.CP.2024.17,
  author =	{Kaznatcheev, Artem and van Marle, Melle},
  title =	{{Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.17},
  URN =		{urn:nbn:de:0030-drops-207021},
  doi =		{10.4230/LIPIcs.CP.2024.17},
  annote =	{Keywords: valued constraint satisfaction problem, steepest ascent, local search, bounded treewidth, intractability}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.35
On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper)

Authors: Jorke M. de Vlas

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
We give a polynomial time algorithm that solves a CSP over 𝐙 with linear inequalities of the form c^{a₁} x - c^{a₂} y ≤ b where x and y are variables, a₁, a₂ and b are parameters, and c is a fixed constant. This is a step in classifying the complexity of CSP(Γ) for first-order reducts Γ from (𝐙, < ,+,1). The algorithm works by first reducing the infinite domain to a finite domain by inferring an upper bound on the size of the smallest solution, then repeatedly merging consecutive constraints into new constraints, and finally solving the problem using arc consistency.
Cite as

Jorke M. de Vlas. On the Complexity of Integer Programming with Fixed-Coefficient Scaling (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 35:1-35:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{devlas:LIPIcs.CP.2024.35,
  author =	{de Vlas, Jorke M.},
  title =	{{On the Complexity of Integer Programming with Fixed-Coefficient Scaling}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{35:1--35:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.35},
  URN =		{urn:nbn:de:0030-drops-207203},
  doi =		{10.4230/LIPIcs.CP.2024.35},
  annote =	{Keywords: constraint satisfaction problems, integer programming, CSP dichotomy}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.43
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs

Authors: Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem [Andrea S. LaPaugh and Christos H. Papadimitriou, 1984] known as the EP problem. Nedev [Zhivko Prodanov Nedev, 1999] proved in 1999, that for directed planar graphs, the problem can be solved in polynomial time. More than two decades since then, we make the first progress in extending the tractable classes of graphs for this problem. We give a polynomial time algorithm to solve the EP problem for classes of H-minor-free directed graphs, where H is a single-crossing graph. We make two new technical contributions along the way, that might be of independent interest. The first, and perhaps our main, contribution is the construction of small, planar, parity-mimicking networks. These are graphs that mimic parities of all possible paths between a designated set of terminals of the original graph. Finding vertex disjoint paths between given source-destination pairs of vertices is another fundamental problem, known to be NP-complete in directed graphs [Steven Fortune et al., 1980], though known to be tractable in planar directed graphs [Alexander Schrijver, 1994]. We encounter a natural variant of this problem, that of finding disjoint paths between given pairs of vertices, but with constraints on parity of the total length of paths. The other significant contribution of our paper is to give a polynomial time algorithm for the 3-disjoint paths with total parity problem, in directed planar graphs with some restrictions (and also in directed graphs of bounded treewidth).
Cite as

Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma. The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.MFCS.2024.43,
  author =	{Chauhan, Archit and Datta, Samir and Gupta, Chetan and Sharma, Vimal Raj},
  title =	{{The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.43},
  URN =		{urn:nbn:de:0030-drops-205992},
  doi =		{10.4230/LIPIcs.MFCS.2024.43},
  annote =	{Keywords: Graph Algorithms, EvenPath, Polynomial-time Algorithms, Reachability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.55
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

Authors: Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.
Cite as

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt. Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goedgebeur_et_al:LIPIcs.MFCS.2024.55,
  author =	{Goedgebeur, Jan and Jooken, Jorik and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and Schaudt, Oliver},
  title =	{{Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55},
  URN =		{urn:nbn:de:0030-drops-206110},
  doi =		{10.4230/LIPIcs.MFCS.2024.55},
  annote =	{Keywords: graph homomorphism, critical graphs, hereditary graph classes}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.73
On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities

Authors: Michał Makowski

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We show that the conditional independence (CI) implication problem with bounded cardinalities, which asks whether a given CI implication holds for all discrete random variables with given cardinalities, is co-NEXPTIME-hard. The problem remains co-NEXPTIME-hard if all variables are binary. The reduction goes from a variant of the tiling problem and is based on a prior construction used by Cheuk Ting Li to show the undecidability of a related problem where the cardinality of some variables remains unbounded. The CI implication problem with bounded cardinalities is known to be in EXPSPACE, as its negation can be stated as an existential first-order logic formula over the reals of size exponential with regard to the size of the input.
Cite as

Michał Makowski. On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{makowski:LIPIcs.MFCS.2024.73,
  author =	{Makowski, Micha{\l}},
  title =	{{On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.73},
  URN =		{urn:nbn:de:0030-drops-206291},
  doi =		{10.4230/LIPIcs.MFCS.2024.73},
  annote =	{Keywords: Conditional independence implication, exponential time, tiling problem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.78
C_{2k+1}-Coloring of Bounded-Diameter Graphs

Authors: Marta Piecyk

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
For a fixed graph H, in the graph homomorphism problem, denoted by Hom(H), we are given a graph G and we have to determine whether there exists an edge-preserving mapping φ: V(G) → V(H). Note that Hom(C₃), where C₃ is the cycle of length 3, is equivalent to 3-Coloring. The question of whether 3-Coloring is polynomial-time solvable on diameter-2 graphs is a well-known open problem. In this paper we study the Hom(C_{2k+1}) problem on bounded-diameter graphs for k ≥ 2, so we consider all other odd cycles than C₃. We prove that for k ≥ 2, the Hom(C_{2k+1}) problem is polynomial-time solvable on diameter-(k+1) graphs - note that such a result for k = 1 would be precisely a polynomial-time algorithm for 3-Coloring of diameter-2 graphs. Furthermore, we give subexponential-time algorithms for diameter-(k+2) and -(k+3) graphs. We complement these results with a lower bound for diameter-(2k+2) graphs - in this class of graphs the Hom(C_{2k+1}) problem is NP-hard and cannot be solved in subexponential-time, unless the ETH fails. Finally, we consider another direction of generalizing 3-Coloring on diameter-2 graphs. We consider other target graphs H than odd cycles but we restrict ourselves to diameter 2. We show that if H is triangle-free, then Hom(H) is polynomial-time solvable on diameter-2 graphs.
Cite as

Marta Piecyk. C_{2k+1}-Coloring of Bounded-Diameter Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{piecyk:LIPIcs.MFCS.2024.78,
  author =	{Piecyk, Marta},
  title =	{{C\underline\{2k+1\}-Coloring of Bounded-Diameter Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{78:1--78:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.78},
  URN =		{urn:nbn:de:0030-drops-206348},
  doi =		{10.4230/LIPIcs.MFCS.2024.78},
  annote =	{Keywords: graph homomorphism, odd cycles, diameter}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.18
Global Benchmark Database

Authors: Markus Iser and Christoph Jabs

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
This paper presents Global Benchmark Database (GBD), a comprehensive suite of tools for provisioning and sustainably maintaining benchmark instances and their metadata. The availability of benchmark metadata is essential for many tasks in empirical research, e.g., for the data-driven compilation of benchmarks, the domain-specific analysis of runtime experiments, or the instance-specific selection of solvers. In this paper, we introduce the data model of GBD as well as its interfaces and provide examples of how to interact with them. We also demonstrate the integration of custom data sources and explain how to extend GBD with additional problem domains, instance formats and feature extractors.
Cite as

Markus Iser and Christoph Jabs. Global Benchmark Database. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 18:1-18:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{iser_et_al:LIPIcs.SAT.2024.18,
  author =	{Iser, Markus and Jabs, Christoph},
  title =	{{Global Benchmark Database}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{18:1--18:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.18},
  URN =		{urn:nbn:de:0030-drops-205405},
  doi =		{10.4230/LIPIcs.SAT.2024.18},
  annote =	{Keywords: Maintenance and Distribution of Benchmark Instances and their Features}
}
  • Refine by Author
  • 10 Papadimitriou, Christos H.
  • 3 Piliouras, Georgios
  • 3 Vazirani, Umesh V.
  • 3 Vidick, Thomas
  • 3 Weinberg, S. Matthew
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Graph algorithms analysis
  • 5 Mathematics of computing → Graph algorithms
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Algorithmic game theory
  • 4 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 Communication Complexity
  • 3 integer programming
  • 2 Approximation Algorithm
  • 2 Blockchain
  • 2 Brain computation
  • Show More...

  • Refine by Type
  • 116 document
  • 1 volume

  • Refine by Publication Year
  • 64 2017
  • 45 2024
  • 3 2019
  • 2 2018
  • 1 2003
  • 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