__fn__'s blog

Need Help on a Graph Problem with Difficulty Around 2400
By __fn__, history, 6 months ago, In English

Problem statement

Given a graph with $$$n$$$ nodes and $$$m$$$ edges,

  • Find a path that starts at a node (the node is not specified).
  • Visit each edge at least once.
  • End the path at the starting node.
  • Minimize the total cost of the tour.

Input

  • The number of nodes $$$n$$$ : $$$2 \leq n \leq 20$$$
  • The number of edges $$$m$$$ : $$$1 \leq m \leq 100$$$.
  • For each edge, provide the source node, destination node, and the cost associated with that edge.

Output

Output the minimum cost of a tour that satisfies the conditions mentioned above.

Note

The path must visit each edge at least once (meaning you can pass the number of time you want), and the tour must end at the starting node.

Can the problem be solved using :

  • $$$dp$$$ with bitmask?
  • min cost max flow?

If you have any solution feel free to comment on it. Thanks!!!

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Question: is the graph weighted since it's asking for cost?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. I have mentioned it as the third point of the input.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this task from?

→ Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

This is the directed version of the Chinese postman problem, which could be solved in O(V2E) via MCMF.

Sorry I get fever and reply to you via a mobile phone on a bed. Search the problem on wiki yourself plz.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your feedback. I found that name somehow yesterday but just realized it is the same. But the approach used for solving it involved minimum weighted perfect matching and Euler tour not MCMF or do it? Also, is there any possible $$$dp$$$ solution for this problem?

    → Reply