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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.