EBElisabet Burjons

Elisabet Burjons

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Elisabet Burjons has a total of 14 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Finding Optimal Solutions with Neighborly Help

    by Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, David Wehner

    Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is $$\text {NP}$$ NP -hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in $$\text {P}$$ P . We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for $$\text {DP}$$ DP (differences of $$\text {NP}$$ NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing $$\beta $$ β -vertex-critical graphs is complete for $$\Theta _2^\text {p}$$ Θ 2 p (parallel access to $$\text {NP}$$ NP ), obtaining the first completeness result for a criticality problem for this class.

  • Delaying Decisions and Reservation Costs

    by Elisabet Burjons, Fabian Frei, Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith


  • Open Access

    Delaying Decisions and Reservation Costs

    by Elisabet Burjons, Fabian Frei, Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith

    We study the Feedback Vertex Set and the Vertex Cover problem in a natural variant of the classical online model that allows for delayed decisions and reservations. Both problems can be characterized by an obstruction set of subgraphs that the online graph needs to avoid. In the case of the Vertex Cover problem, the obstruction set consists of an edge (i.e., the graph of two adjacent vertices), while for the Feedback Vertex Set problem, the obstruction set contains all cycles. In the delayed-decision model, an algorithm needs to maintain a valid partial solution after every request, thus allowing it to postpone decisions until the current partial solution is no longer valid for the current request. The reservation model grants an online algorithm the new and additional option to pay a so-called reservation cost for any given element in order to delay the decision of adding or rejecting it until the end of the instance. For the Feedback Vertex Set problem, we first analyze the variant with only delayed decisions, proving a lower bound of $4$ and an upper bound of $5$ on the competitive ratio. Then we look at the variant with both delayed decisions and reservation. We show that given bounds on the competitive ratio of a problem with delayed decisions impliy lower and upper bounds for the same problem when adding the option of reservations. This observation allows us to give a lower bound of $\min{\{1+3α,4\}}$ and an upper bound of $\min{\{1+5α,5\}}$ for the Feedback Vertex Set problem. Finally, we show that the online Vertex Cover problem, when both delayed decisions and reservations are allowed, is $\min{\{1+2α, 2\}}$-competitive, where $α\in \mathbb{R}_{\geq 0}$ is the reservation cost per reserved vertex.

  • Open Access

    Reoptimization of parameterized problems

    by Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith

    Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We combine both techniques, in order to better classify the complexity of problems in the parameterized setting. Specifically, we see that some problems in the class of compositional problems, which do not have polynomial kernels under standard complexity-theoretic assumptions, do have polynomial kernels under the reoptimization model for some local modifications. We also observe that, for some other local modifications, these same problems do not have polynomial kernels unless $$\mathbf{NP}\subseteq \mathbf{coNP/poly}$$ NP ⊆ coNP / poly . We find examples of compositional problems, whose reoptimization versions do not have polynomial kernels under any of the considered local modifications. Finally, in another negative result, we prove that the reoptimization version of Connected Vertex Cover does not have a polynomial kernel unless Set Cover has a polynomial compression. In a different direction, looking at problems with polynomial kernels, we find that the reoptimization version of Vertex Cover has a polynomial kernel of size $$\varvec{2k+1}$$ 2 k + 1 using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.


  • Open Access

    Online Simple Knapsack with Reservation Costs

    by Hans-Joachim Boeckenhauer, Elisabet Burjons, Fabian Frei, Juraj Hromkovic, Henri Lotze, Peter Rossmanith

    In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the knapsack without any knowledge about the rest of the instance. The goal is to pack the knapsack as full as possible. In this work, we introduce the option of reserving items for the cost of a fixed fraction $\alpha$ of their size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject these items until after the last item of the instance was presented. While the classical online simple knapsack problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive. We give tight bounds for the whole range of $\alpha$ from $0$ to $1$.

  • The Secretary Problem with Reservation Costs

    by Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith


  • Open Access

    From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata

    by Elisabet Burjons, Fabian Frei, Martin Raszyk

    The question whether P equals NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem for finite transducers and automata. Every nondeterministic finite transducer defines a binary relation associating each input word with all output words that the transducer can successfully produce on the given input. Finite-valued transducers are those for which there is a finite upper bound on the number of output words that the relation associates with every input word. We characterize finite-valued, functional, and unambiguous nondeterministic transducers whose relations can be verified by a deterministic two-tape automaton, show how to construct such an automaton if one exists, and prove the undecidability of the criterion.

  • Open Access

    Reoptimization of Parameterized Problems

    by Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith

    Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We try to combine both techniques, in order to better classify the complexity of problems in the parameterized setting. Specifically, we see that some problems in the class of compositional problems, which do not have polynomial kernels under standard complexity-theoretic assumptions, do have polynomial kernels under reoptimization for some local modifications. Moreover, we find that the reoptimization version of Vertex Cover has a polynomial kernel of size 2k using crown decomposition. Finally, in a negative result, we prove that the reoptimization version of Connected Vertex Cover does not have a Turing kernelization unless Set Cover has a polynomial kernel

  • The k-Server Problem with Advice in d Dimensions and on the Sphere

    by Elisabet Burjons, Dennis Komm, Marcel Schöngens