# Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

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

• So this is a variant of "maximum edge-disjoint paths" – Bjørn Kjos-Hanssen Sep 28 '18 at 7:24
• Yes, but requiring at least k matches in two paths – user3508551 Sep 28 '18 at 9:21
• 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? – Saeed Sep 28 '18 at 16:16
• 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 – user3508551 Sep 28 '18 at 16:22