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
    • Sub-Exponential Approximate and Parameterized Algorithms; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0022
    • 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

    Consultation statistics

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