TY - GEN

T1 - New results on directed edge dominating set

AU - Belmonte, Rémy

AU - Hanaka, Tesshu

AU - Katsikarelis, Ioannis

AU - Kim, Eun Jung

AU - Lampis, Michael

N1 - Publisher Copyright:
© Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 just by tw, 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.

AB - 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 just by tw, 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.

UR - http://www.scopus.com/inward/record.url?scp=85053177409&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053177409&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2018.67

DO - 10.4230/LIPIcs.MFCS.2018.67

M3 - Conference contribution

AN - SCOPUS:85053177409

SN - 9783959770866

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

A2 - Potapov, Igor

A2 - Worrell, James

A2 - Spirakis, Paul

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

Y2 - 27 August 2018 through 31 August 2018

ER -