New Results on Directed Edge Dominating Set
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 s...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5378/pdf |
| _version_ | 1797270012733423616 |
|---|---|
| author | Rémy Belmonte Tesshu Hanaka Ioannis Katsikarelis Eun Jung Kim Michael Lampis |
| author_facet | Rémy Belmonte Tesshu Hanaka Ioannis Katsikarelis Eun Jung Kim Michael Lampis |
| author_sort | Rémy Belmonte |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T21:30:54Z |
| format | Article |
| id | doaj.art-804a99ed163d4f95b99b4ae8a732ba86 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:30Z |
| publishDate | 2023-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-804a99ed163d4f95b99b4ae8a732ba862024-03-07T15:48:03ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-03-01vol. 25:110.46298/dmtcs.53785378New Results on Directed Edge Dominating SetRémy BelmonteTesshu Hanakahttps://orcid.org/0000-0001-6943-856XIoannis KatsikarelisEun Jung KimMichael LampisWe 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.https://dmtcs.episciences.org/5378/pdfcomputer science - computational complexitycomputer science - data structures and algorithms |
| spellingShingle | Rémy Belmonte Tesshu Hanaka Ioannis Katsikarelis Eun Jung Kim Michael Lampis New Results on Directed Edge Dominating Set Discrete Mathematics & Theoretical Computer Science computer science - computational complexity computer science - data structures and algorithms |
| title | New Results on Directed Edge Dominating Set |
| title_full | New Results on Directed Edge Dominating Set |
| title_fullStr | New Results on Directed Edge Dominating Set |
| title_full_unstemmed | New Results on Directed Edge Dominating Set |
| title_short | New Results on Directed Edge Dominating Set |
| title_sort | new results on directed edge dominating set |
| topic | computer science - computational complexity computer science - data structures and algorithms |
| url | https://dmtcs.episciences.org/5378/pdf |
| work_keys_str_mv | AT remybelmonte newresultsondirectededgedominatingset AT tesshuhanaka newresultsondirectededgedominatingset AT ioanniskatsikarelis newresultsondirectededgedominatingset AT eunjungkim newresultsondirectededgedominatingset AT michaellampis newresultsondirectededgedominatingset |