# Tag Info

## Hot answers tagged computational-complexity

13

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases. Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer ...

7

You could try to solve it as a min cost flow problem. NetworkX is a package for graph algorithms and has algorithms for this implemented. It can easily be installed via pip install networkx. An minimal working example is given at the bottom of this link: https://networkx.github.io/documentation/networkx-2.4/reference/algorithms/generated/networkx....

5

It is NP-hard: Bruno Codenotti, Ivan Gerace, Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra and its Applications 285 (1-3), pages 123-142, 1998, pdf Other Cayley graphs have been studied by Chris Godsil and Brendan Rooney in the paper Hardness of Computing Clique Number and Chromatic ...

5

If only a subset of nodes is to be transfered, and that the cardinality of this subset is undefined, then I agree with @LocalSolver. Otherwise (if all nodes have to be transfered $1$ by $1$), I believe the problem is not NP-hard (nor NP-complete): Consider the following graph : Create a first layer with the $n$ nodes. Create a second layer with $n \times n$ ...

5

Let us get some additional insights by assuming $d_{ij} \in \{0,1\}$ and interpreting the data as a directed graph. For now we assume the number of $i$'s and $j$'s is the same, but I don't think it will be difficult to generalize that assumption. We say there is an arc from $i$ to $j$ iff $d_{ij} \neq 0$. Now for each vertex $j$ where $s_j \neq 0$, we have ...

5

The problem is NP-hard because it can be used to solve the subset-sum problem: Subset-sum: given a set of numbers $a_k\forall k\in K$ and a special number $b$ is there a subset of numbers $K' \subset K$ such that $\sum_ {k\in K'} a_k =b$ Reduction: let $j \in \{1,2\}$, and $s_1=b$ $d_{k,j} = a_k \forall k,j$ and $s_2=\sum_i a_i - b$ I don't know of any ...

4

For a linear program in standard form \begin{align} \min_{x} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b,\\ & x \geq 0, \end{align} where the constraint matrix $A \in \mathbb{R}^{m \times n}$ (i.e., $m$ constraints and $n$ variables) has full row rank (which implies $n \geq m$), the best-known interior-point algorithms require $O(\sqrt{n} \log(1/\... 4 i would assume, that there doesn't even exist an optimal solution. You want to have$\epsilon$-flow across every edge to collect all the cost$b_{uv}$. On the other hand you want to maximize the flow across the edges with the highest cost$c_{uv}$. This leads to pressure to have$\epsilon$as small as possible, while still$\epsilon > 0$. Such an$\...

4

You are correct, you have to look at the variables' ranges. $z_t$ is defined $\forall t \in T$, so you have $|T| \in O(|T|)$ such variables; $y_i^k$ is defined $\forall i \in [1,n], \; \forall k \in [1,n]$, so you have $n^2 \in O(n^2)$ such variables; $x_{ij}^k$ is defined $\forall (i,j) \in [1,n]\times [1,n], i < j, \; \forall k \in [1,n]$, so you have $... 3 The general strategy is as follows: For each node, determine its in-degree. Locate those nodes for which the in-degree is zero have no incoming edges (there will always be some since this is a DAG). Add those nodes to a queue. Pop nodes from the queue and process them. For each node popped from the queue, decrement the in-degree count of its "... 3 As nicely mentioned above by @Kuifje, the problem can be reduced to a minimum-cost maximum flow problem if all the nodes have to be transferred. If only a subset of the nodes has to be transferred then this is a graph partitioning problem known: partitioning the vertices of a graph into two subsets such that the weight of the cut between the two subsets is ... 3 There are a number of possible explanations (not mutually exclusive). The larger model might have a tighter continuous relaxation. (You can test that by relaxing the integrality restrictions and solving both LPs.) Assuming you are using a solver that has a presolve stage, there may be something in the first model that allows the presolver to tighten things ... 3 I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing$\leq$to$=$in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ... 3 You can rewrite the maximum cost flow problem with objective $$\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$$ as a minimum cost flow problem with objective $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ for the concave function$g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} ...

3

You can conclude There exists no PTAS for Problem P1 if $P \neq NP$, but you can NOT conclude P1 is APX-hard. Precisely: If someone proofs $P = NP$ you get a trivial PTAS; Assumung $P \neq NP$, it still could be APX-intermediate (see https://en.wikipedia.org/wiki/APX#APX-intermediate).

2

You can try CBC which uses Dual Simplex (the same algorithm CPLEX & GUROBI use). The easiest way to use that through Python is Pyomo.

1

As I did not see how one would have to choose the weights in @Kuifje answer I started thinking about the problem as well and I came to the conclusion that it is NP hard. The proof uses reduction of graph partitioning and goes as follows. Let $G = (V,E)$ with $n:=|V|$ even be the graph that we want to find the minimal graph partitioning of. Create an instance ...

1

This is an interesting one. You could bring your graph into Reverse Polish Notation form, which allows you to create a stack of nodes and evaluate in one vector pass. For what you want to do, you don't care about evaluation per se, but you can attach a "number of descendants" property to your nodes and propagate that organically as you would ...

1

How about something like this: Copy the adjacency matrix. Count the out-valence of each node. Find all nodes X with 0 out-valence. Repeat until done: For each node Y where Y→X is an edge: Merge row X into row Y. Reduce Y's out-valence by one. Next X set will be the Y's whose out-valance just became 0. Each row of the resulting matrix will contain all ...

Only top voted, non community-wiki answers of a minimum length are eligible