2
$\begingroup$

What is known about the complexity of solving (or approximately solving) the following problem?

INPUT: Graph $G=(V,E)$ and constants $L$ and $K$.

OUTPUT: The maximum size of any set $S$ of simple paths of length $L$ such that every two paths in $S$ differ in at least $K$ edges. I care about the case when $L$ and $K$ are small constants

$\endgroup$
  • $\begingroup$ So this is a variant of "maximum edge-disjoint paths" $\endgroup$ – Bjørn Kjos-Hanssen Sep 28 '18 at 7:24
  • $\begingroup$ Yes, but requiring at least k matches in two paths $\endgroup$ – user3508551 Sep 28 '18 at 9:21
  • $\begingroup$ If you can count the number of paths of length $n$ in polynomial time then you can solve Hamiltonian path problem. Is there a bound on the length of paths? I mean is $n$ a fixed value or it is part of input? $\endgroup$ – Saeed Sep 28 '18 at 16:16
  • $\begingroup$ Saeed in my case $n$ and $d$ are both fixed and the graph is known. I just need to count how many of these paths are there $\endgroup$ – user3508551 Sep 28 '18 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.