# Tagged Questions

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

20 views

### A graph is said to be in Hamiltonian cycle. Then the travelling salesman problem is? [on hold]

The graph ‘g’ with vertices {A, B, C, D, E } is said to be in Hamiltonian cycle. Then the travelling salesman problem is Heuristic NP-complete minimal spanning tree triangle inequality My ...
71 views

### Find solutions of $a + b + c$ even, $3a + 2b - 3c$ odd, $a - 7b + 8c$ odd, in polynomial time

Suppose I have a linear equation in $3$ variables $a$, $b$ and $c$. \begin{align} \begin{cases} a + b + c &= 40 \\ 3a + 2b - 3c &= 49 \\ a - 7b + 8c &= 77 \end{cases} \end{align} The ...
19 views

### Polynomial time reduction Hampath to TSP

is there a polynomial time reduction from Hamiltonian Path to TSP? If so, could you tell me? Thank you in advance! Toby
56 views

### Difference between NP-hard and NP-complete

I am struggling to tell the difference between the definitions of NP-hard and NP-complete problems. I know that NP-complete problems are NP-hard, so this tells me that \text{$P_1$ polynomially ...
53 views

### Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
33 views

### Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
32 views

### Optimization algorithms for Distribution and Logistics scenario

I am looking for a way to express the following logistics/distribution problem as an equation that can be run thru a solver to find an approximate solution. The problems is described as follows: ...
58 views

### Prove that Topological sort with constraints is NP-complete

This question is a followup to: Heuristics for topological sort I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total ...