<p>What is known about the complexity of solving (or approximately solving) the following problem? </p>

<p>INPUT: Graph <span class="math-container">$G=(V,E)$</span> and constants <span class="math-container">$L$</span> and <span class="math-container">$K$</span>. </p>

<p>OUTPUT: The maximum size of any set <span class="math-container">$S$</span> of simple paths of length <span class="math-container">$L$</span> such that every two paths in <span class="math-container">$S$</span> differ in at least <span class="math-container">$K$</span> edges. I care about the case when <span class="math-container">$L$</span> and <span class="math-container">$K$</span> are small constants</p>

CC BY-SA 4.0
2018-09-28T07:24:07.540Z
So this is a variant of "maximum edge-disjoint paths"
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-09-28T09:21:54.863Z
Yes, but requiring at least k matches in two paths
user3508551
CC BY-SA 4.0
2018-09-28T16:16:33.183Z
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
CC BY-SA 4.0
2018-09-28T16:22:37.110Z
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
<graph-algorithms><np-hardness><approximation-algorithms>
Counting the maximum number of paths of length $n$ that differ in at least $k$ edges
user3508551
# Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

(Asked by: username_0 on 2018-09-28)

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

**Tags:** graph-algorithms, np-hardness, approximation-algorithms
> **Comments:**
> **username_1**: So this is a variant of "maximum edge-disjoint paths"  
> **username_0**: Yes, but requiring at least k matches in two paths  
> **username_2**: 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?  
> **username_0**: 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  

---

## 0 answers

