LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Advanced search

Search results

Result 1 - 9 of total 9

Search options

  1. Book ; Online: On the Exact Matching Problem in Dense Graphs

    Maalouly, Nicolas El / Haslebacher, Sebastian / Wulf, Lasse

    2024  

    Abstract: In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly k red edges. Since 1987 it is known that the Exact Matching Problem can ... ...

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

    Comment: 40 pages, 13 figures, submitted to STACS 2024
    Keywords Computer Science - Computational Complexity
    Subject code 511 ; 004
    Publishing date 2024-01-08
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  2. Book ; Online: Recognition of Unit Segment and Polyline Graphs is $\exists\mathbb{R}$-Complete

    Hoffmann, Michael / Miltzow, Tillmann / Weber, Simon / Wulf, Lasse

    2024  

    Abstract: Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments ... ...

    Abstract Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are $\exists\mathbb{R}$-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is $\exists\mathbb{R}$-complete.

    Comment: 18 pages, 15 figures
    Keywords Computer Science - Computational Geometry
    Publishing date 2024-01-04
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  3. Article: Non-Preemptive Tree Packing.

    Lendl, Stefan / Woeginger, Gerhard / Wulf, Lasse

    Algorithmica

    2022  Volume 85, Issue 3, Page(s) 783–804

    Abstract: An instance of the non-preemptive tree packing problem consists of an undirected ... ...

    Abstract An instance of the non-preemptive tree packing problem consists of an undirected graph
    Language English
    Publishing date 2022-08-23
    Publishing country United States
    Document type Journal Article
    ZDB-ID 1458414-1
    ISSN 1432-0541 ; 0178-4617
    ISSN (online) 1432-0541
    ISSN 0178-4617
    DOI 10.1007/s00453-022-01026-7
    Database MEDical Literature Analysis and Retrieval System OnLINE

    Full text online

    More links

    Kategorien

    Order via subito

    This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

  4. Book ; Online: An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs

    Dürr, Anita / Maalouly, Nicolas El / Wulf, Lasse

    2023  

    Abstract: In 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph $G$ and an integer $k$ one has to decide whether there exists a perfect matching in $G$ with exactly $k$ red edges. Even though a ...

    Abstract In 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph $G$ and an integer $k$ one has to decide whether there exists a perfect matching in $G$ with exactly $k$ red edges. Even though a randomized polynomial-time algorithm for this problem was quickly found a few years later, it is still unknown today whether a deterministic polynomial-time algorithm exists. This makes the Exact Matching problem an important candidate to test the RP=P hypothesis. In this paper we focus on approximating Exact Matching. While there exists a simple algorithm that computes in deterministic polynomial-time an almost perfect matching with exactly $k$ red edges, not a lot of work focuses on computing perfect matchings with almost $k$ red edges. In fact such an algorithm for bipartite graphs running in deterministic polynomial-time was published only recently (STACS'23). It outputs a perfect matching with $k'$ red edges with the guarantee that $0.5k \leq k' \leq 1.5k$. In the present paper we aim at approximating the number of red edges without exceeding the limit of $k$ red edges. We construct a deterministic polynomial-time algorithm, which on bipartite graphs computes a perfect matching with $k'$ red edges such that $k/3 \leq k' \leq k$.
    Keywords Computer Science - Data Structures and Algorithms ; F.2.0
    Subject code 005
    Publishing date 2023-07-05
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  5. Book ; Online: Exact Matching

    Maalouly}, Nicolas {El / Steiner, Raphael / Wulf, Lasse

    Correct Parity and FPT Parameterized by Independence Number

    2022  

    Abstract: Given an integer $k$ and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly $k$ of its edges are red. Soon after Papadimitriou and Yannakakis (JACM ... ...

    Abstract Given an integer $k$ and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly $k$ of its edges are red. Soon after Papadimitriou and Yannakakis (JACM 1982) introduced the problem, a randomized polynomial-time algorithm solving the problem was described by Mulmuley et al. (Combinatorica 1987). Despite a lot of effort, it is still not known today whether a deterministic polynomial-time algorithm exists. This makes the exact matching problem an important candidate to test the popular conjecture that the complexity classes P and RP are equal. In a recent article (MFCS 2022), progress was made towards this goal by showing that for bipartite graphs of bounded bipartite independence number, a polynomial time algorithm exists. In terms of parameterized complexity, this algorithm was an XP-algorithm parameterized by the bipartite independence number. In this article, we introduce novel algorithmic techniques that allow us to obtain an FPT-algorithm. If the input is a general graph we show that one can at least compute a perfect matching $M$ which has the correct number of red edges modulo 2, in polynomial time. This is motivated by our last result, in which we prove that an FPT algorithm for general graphs, parameterized by the independence number, reduces to the problem of finding in polynomial time a perfect matching $M$ with at most $k$ red edges and the correct number of red edges modulo 2.
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Computational Complexity
    Subject code 511
    Publishing date 2022-07-20
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  6. Book ; Online: A linear time algorithm for linearizing quadratic and higher-order shortest path problems

    Çela, Eranda / Klinz, Bettina / Lendl, Stefan / Woeginger, Gerhard J. / Wulf, Lasse

    2023  

    Abstract: An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides ... ...

    Abstract An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.
    Keywords Computer Science - Data Structures and Algorithms ; F.2.2 ; G.2.2
    Publishing date 2023-03-01
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  7. Book ; Online: Two-Stage Robust Optimization Problems with Two-Stage Uncertainty

    Goerigk, Marc / Lendl, Stefan / Wulf, Lasse

    2021  

    Abstract: We consider two-stage robust optimization problems, which can be seen as games between a decision maker and an adversary. After the decision maker fixes part of the solution, the adversary chooses a scenario from a specified uncertainty set. Afterwards, ... ...

    Abstract We consider two-stage robust optimization problems, which can be seen as games between a decision maker and an adversary. After the decision maker fixes part of the solution, the adversary chooses a scenario from a specified uncertainty set. Afterwards, the decision maker can react to this scenario by completing the partial first-stage solution to a full solution. We extend this classic setting by adding another adversary stage after the second decision-maker stage, which results in min-max-min-max problems, thus pushing two-stage settings further towards more general multi-stage problems. We focus on budgeted uncertainty sets and consider both the continuous and discrete case. For the former, we show that a wide range of robust combinatorial optimization problems can be decomposed into polynomially many subproblems, which can be solved in polynomial time for example in the case of (representative) selection. For the latter, we prove NP-hardness for a wide range of problems, but note that the special case where first- and second-stage adversarial costs are equal can remain solvable in polynomial time.
    Keywords Mathematics - Optimization and Control ; Computer Science - Discrete Mathematics ; Computer Science - Data Structures and Algorithms
    Subject code 510
    Publishing date 2021-04-07
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  8. Book ; Online: Assistance and Interdiction Problems on Interval Graphs

    Hoang, Hung P. / Lendl, Stefan / Wulf, Lasse

    2021  

    Abstract: We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the ...

    Abstract We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor is allowed to replace up to $k$ original intervals with their replacements. Using this framework we also study the contrary of interdiction problems which we call assistance problems. We study these problems for the independence number, the clique number, shortest paths, and the scattering number. We obtain polynomial time algorithms for most of the studied problems. Via easy reductions, it follows that on interval graphs, the most vital nodes problem with respect to shortest path, independence number and Hamiltonicity can be solved in polynomial time.
    Keywords Computer Science - Data Structures and Algorithms ; Mathematics - Optimization and Control
    Subject code 511
    Publishing date 2021-07-30
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  9. Book ; Online: Recoverable Robust Representatives Selection Problems with Discrete Budgeted Uncertainty

    Goerigk, Marc / Lendl, Stefan / Wulf, Lasse

    2020  

    Abstract: Recoverable robust optimization is a multi-stage approach, where it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this approach for a class of selection problems. The aim is to choose a fixed ... ...

    Abstract Recoverable robust optimization is a multi-stage approach, where it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this approach for a class of selection problems. The aim is to choose a fixed number of items from several disjoint sets, such that the worst-case costs after taking a recovery action are as small as possible. The uncertainty is modeled as a discrete budgeted set, where the adversary can increase the costs of a fixed number of items. While special cases of this problem have been studied before, its complexity has remained open. In this work we make several contributions towards closing this gap. We show that the problem is NP-hard and identify a special case that remains solvable in polynomial time. We provide a compact mixed-integer programming formulation and two additional extended formulations. Finally, computational results are provided that compare the efficiency of different exact solution approaches.
    Keywords Mathematics - Optimization and Control ; Computer Science - Computational Complexity
    Subject code 510
    Publishing date 2020-08-28
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top