The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged


Dominating Set and Independent Dominating Set are NP-hard on paths if there is also in the input a "conflict graph", where an edge in this graph is a pair of vertices which cannot be both in the solution. Cornet, Alexis; Laforest, Christian, Domination problems with no conflicts, Discrete Appl. Math. 244, 78-88 (2018). ZBL1387.05181.


The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial ...

Top 50 recent answers are included