Rémy Belmonte ; Tesshu Hanaka ; Ioannis Katsikarelis ; Eun Jung Kim ; Michael Lampis - New Results on Directed Edge Dominating Set

dmtcs:5378 - Discrete Mathematics & Theoretical Computer Science, March 10, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.5378
New Results on Directed Edge Dominating SetArticle

Authors: Rémy Belmonte ; Tesshu Hanaka ORCID; Ioannis Katsikarelis ; Eun Jung Kim ; Michael Lampis

    We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p,q)-Edge Dominating Set. In this problem an arc (u,v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0,1)-dEDS and (1,1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p,q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized by tw (even if the size of the optimal is added as a second parameter), where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p,q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.


    Volume: vol. 25:1
    Published on: March 10, 2023
    Accepted on: January 5, 2023
    Submitted on: April 14, 2019
    Keywords: Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms
    Funding:
      Source : OpenAIRE Graph
    • Algorithms with Small Separations acKnowledged: graphs and linear matroids; Funder: French National Research Agency (ANR); Code: ANR-18-CE40-0025
    • Efficiency and Structure in Graph Mining Applications; Funder: French National Research Agency (ANR); Code: ANR-17-CE23-0010
    • Sub-Exponential Approximate and Parameterized Algorithms; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0022

    Consultation statistics

    This page has been seen 1100 times.
    This article's PDF has been downloaded 794 times.