Workshop on
Efficient Algorithms, Automata and Data Structures

09:00-09:30 (room: SJ1Z17T/VKM)

Peter Mlynárčik: Nondeterministic complexity of operations on free and convex languages

We study the nondeterministic state complexity of basic regular operations on the classes of prefix-, suffix-, factor-, and subword-free and -convex regular languages. For the operations of union, intersection, complementation, concatenation, square, star, and reversal, we get the tight upper bounds for all considered classes except for complementation on factor- and subword-convex languages. Most of our witnesses are described over optimal alphabets. The most interesting result is the describing of a proper suffix-convex language over a five-letter alphabet meeting the upper bound 2ⁿ for complementation.

09:30-10:00 (room: SJ1Z17T/VKM)

Viliam Geffert: Languages in alternating O(loglog n) space

We shall present some new simulations for ASpace(loglog n), the class of languages accepted by alternating Turing machines with O(loglog n) space and their consequences for higher complexity classes. We shall also present solutions of some open problems and some problems related to ASpace(loglog n) not solved yet.

10:30-11:30 (room: SJ1Z17T/VKM)

Stefan Popescu: A survey on networks of polarized evolutionary processors

We consider a bio-inspired computing model: namely a variant of networks of evolutionary processors, where each processor and the data navigating through the network are considered to be polarized. While the polarity of the processors is predefined, the polarity of each string is dynamically computed, allowing the flow of the data through the network. We give examples on how this computing model can be used to solve NP-Complete problems. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be efficiently simulated by these networks with the number of nodes depending linearly on the tape alphabet of the Turing machine. We also propose two different ideas on how to simulate a non-deterministic Turing machine using a network with a constant number of nodes, but at a loss in time complexity.

11:30-12:00 (room: SJ1Z17T/VKM)

Galina Jirásková: On the descriptional complexity of the forever operator

Motivated by restricted temporal logic, the forever (=not eventually not) operator has been investigated by Jean-Camille Birget in 1996. He obtained the upper and lower bounds on the nondeterministic state complexity of this operator. We improve this result and get the exact nondeterministic complexity. We also study different trade-offs for this operator: Assuming that an operand is given by deterministic, partial deterministic, nondeterministic, nondeterministic with multiple initial states, alternating, or boolean finite automaton, we ask how many states are sufficient and necessary in the worst case for an automaton of one of this six models to accept the result of the forever operator. We get the exact trade-offs in 32 out of 36 cases. One of the most interesting results is the NFA-to-DFA trade-off given by Dedekind number which counts the number of antichains of subsets of a finite set.

13:00-13:45 (room: SJ1Z17T/VKM)

Iztok Peterin: Recognizing generalized Sierpiński graphs

Let H be an arbitrary graph with vertex set V(H)=[n_H]={1,...,n_H}. The generalized Sierpiński graph S_Hⁿ, n ∊ N, is defined on the vertex set [n_H]ⁿ, two different vertices u =u_n ... u₁ and v = v_n...v₁ being adjacent if and only if there exists an h ∊ [n] such that

• u_t = v_t, for t>h,
• u_h ≠ v_h and u_hv_h ∊ E(H), and
• u_t = v_h and v_t = u_h for t<h.

If H is isomorphic to a complete graph K_t, then we speak of the Sierpiński graph S_Ktⁿ. We present an algorithm that recognizes Sierpiński graphs S_Ktⁿ in O(|V(S_Ktⁿ)|^1+1/n) time. A polynomial time algorithm is given for generalized Sierpiński graphs when H belong to a certain graph class. We also describe how to derive a base graph H from an arbitrary S_Hⁿ.
This is a joint work with Wilfried Imrich.

13:45-14:30 (room: SJ1Z17T/VKM)

Zsuzsi Jankó: Trading networks with bilateral contracts

We consider general networks of bilateral contracts that include supply chains. We define a new stability concept, called trail stability, and show that any network of bilateral contracts has a trail- stable outcome whenever agents' choice functions satisfy full substitutability. Trail stability is a natural extension of chain stability, but is a stronger solution concept in general contract networks. Trail-stable outcomes are not immune to deviations of arbitrary sets of firms. We show that trail-stable outcomes always exist, For trail- stable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategy-proofness and comparative statics of firm entry and exit. We then describe the relationships between various other concepts.
Joint work with Tamás Fleiner, Alexander Teytelboym and Akihisa Tamura.

15:00-15:45 (room: SJ1Z17T/VKM)

Ronald de Haan: Pareto optimal allocation under uncertain preferences

The assignment problem is one of the most well-studied settings in social choice, matching, and discrete allocation. We consider this problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference profiles. For both of these models, we present a number of algorithmic and complexity results highlighting the difference and similarities in the complexity of the two models.
Joint work with Haris Aziz and Baharak Rastegari.

15:45-16:15 (room: SJ1Z17T/VKM)

Gabriel Semanišin: Recent progress in k-path vertex cover problem

A subset of the vertex set of a graph G is called k-Path Vertex Cover Set if it intersects all path of order k in G. This concept was introduced by 2011 by B. Brešar, F. Kardoš, J. Katrenič and G. Semanišin as a generalisation of the well known Vertex Cover Problem. The concept became quite atractive and was investigated by many authors. In our contribution we summarise recent develepment in this area.

9:30-10:30 (room: SJ1Z17T/VKM)

Katarína Cechlárová: Fair division of a graph

We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases where the underlying graph has simple structure, and/or the number of agents-or, less restrictively, the number of agent types-is small. In particular, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently. In the second part of the talk we deal with the situation when the items are undesirable.

10:45-11:45 (room: SJ1Z17T/VKM)

Péter Biró: Stable matching with uncertain preferences

We study the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. The talk will be based on two papers. In the first, we consider three models of uncertainty: (1) lottery model — in which for each agent, there is a probability distribution over linear preferences, (2) compact indifference model — for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model — there is a lottery over preference profiles. In the second paper we consider (4) pairwise preferences - in which the agents have probabilistic pairwise comparisons over their possible partners that may be intransitive. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant. Joint work with Haris Aziz, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari.