5
$\begingroup$

During an article I am writing, I encountered the following problem: Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$. Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.

Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in polynomial time.

I tried to search "Google Scholar" and use variations of the cycle canceling (and other min cost flow) algorithms to solve the problem but with no successes.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

After I posted the question in cstheory, I received an answer there.

Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.

Improve this answer
$\endgroup$
0
$\begingroup$

I don't know of any existing algorithm, but perhaps you could think of some approach like:

  1. Try some random triangles, pick a low flow cost circulation w
  2. Remove all edges with weight > w
  3. If there is any node with degree just 2, remove the node and add the weights of the edges to create a new (longer) edge
  4. Repeat steps 2 and 3, if possible
  5. Start from the beginning with the new graph

You cannot get any closer to your final result when all the weights are pretty similar (differing about 3 times). So this seems like you should be able to get at least some O(1) approximation.

To get what the nodes were in the original graph, you have to remember which nodes were deleted from the middle of which edges and add them back afterwards.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Not sure such algorithm will work. Consider for example a triangle-free graph $G$, where every node has degree >= 3. In such case, the algorithm will terminate, with no flow augmentation. $\endgroup$
    – user3563894
    Jul 21, 2018 at 16:53
  • $\begingroup$ True, true, the graph would need to have cycles of constant length (then it could be random cycles of that size). If the smallest cycle is more, then approximation would also be more. $\endgroup$
    – Mederr
    Jul 21, 2018 at 16:55
  • $\begingroup$ stackoverflow.com/questions/3911626/… ? $\endgroup$
    – Mederr
    Jul 21, 2018 at 17:00
  • $\begingroup$ Do you think that such algorithm might be a $O(1)$ approximation? $\endgroup$
    – user3563894
    Jul 21, 2018 at 17:00
  • 1
    $\begingroup$ i think the one in the link is not approximation at all, so no need to bother approximating anymore. But then there is the r issue... $\endgroup$
    – Mederr
    Jul 21, 2018 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.