2
$\begingroup$

Consider the following inequalities:

$\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$

$\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$

$x_{ij} \ge 0 \;\;\; i,j=1,...,n$

$y_i \in \{0,1,2\} \,\,\,\, i=1,...,n$

  • $a_{ij}$ are 0-1 coefficient
  • $x_{ij}$ are unknowns.
  • $y_i$ are integral unknowns. Each $y_i$ can only take on integer value $0,1,2$.

Let $\textbf{y}$ be the vector of $(y_1,...,y_n)$. I want to count how many different $\textbf{y}$'s (if two $\textbf{y}$'s differ in at least one $i$ then they are different) such the above problem is feasible (there exists at least one $\textbf{x}$ satiesfies above inequalities)?

You can think of an $n$ by $n$ matrix $A$ with each entry equals to $a_{ij}x_{ij}$. Each row sum must be 1 and each column sum must be less than or equal to $y_i$. You can also think the problem as a bipartite graph $G=(V_1 \cup V_2 ,E)$ with incidence matrix $[a_{ij}]$. The problem is feasible if there is a special matching such as all nodes in $V_1$ are matched exactly once and all nodes in $V_2$ are matched at most $y_i$ times. (if $x_{ij}$ are restricted to binary, which I don't care)

Is this counting problem #P-complete?

edit: This problem is a special case of my another question Complexity class of maximum flow problem with random arc capacity which no one has answered yet. If anyone has relevant reference for the original question too I'll appreciate it.

To clarify the problem a little bit more, the problem has

INPUT: $a_{ij}$

OUTPUT: Number of different $\textbf{y}$'s that above inequalities are satisfied.

I am not an expert in complexity theory, but I tried to dig around the problem of counting the number of matchings in a bipartite graph, which is closely related to #P. I have no success because there is a gap between the number of matchings and the number of different $\textbf{y}$'s. Different matchings can correspond to the same $\textbf{y}$ (and of course the same matching can be satisfied by different $\textbf{y}$'s).

$\endgroup$
  • 1
    $\begingroup$ Hard counting problems usually have an input other than $n$. In this case, the problem may be difficult for trivial reasons – the number of solutions is very large compared to the size of $n$. $\endgroup$ – Yuval Filmus Feb 19 '16 at 5:15
  • 1
    $\begingroup$ 1. Can you edit the question to be a little bit clearer about what the input is and what the algorithmic task is? Do you want an algorithm that takes as input the $a_{ij}$'s and outputs the number of vectors $y$ such that there exists a vector $x$ satisfying the above equations? Are the $x$'s required to be integers? 2. What have you tried? Have you tried looking for a reduction from another #P-complete problem? What ones have you tried? $\endgroup$ – D.W. Feb 19 '16 at 6:05
  • $\begingroup$ @YuvalFilmus I actually have a question about this. For example, if I want to count the number of different n-dimensional non-negative integral vector $\textbf{x}$ such that $\sum x_i=k$. The answer is $k+n-1$ choose $n-1$, which is large compared to $n$, but this is not a hard counting problem. Why my problem is trivially hard? $\endgroup$ – Yang Wang Feb 19 '16 at 18:41
  • $\begingroup$ @D.W. I have edited my question. For $\textbf{x}$, if thinking the problem as matching then you need $x$ to be binary, but there may be other ways to attack the problem which don't need $x$ to be binary. I am OK with both. $\endgroup$ – Yang Wang Feb 19 '16 at 18:46
  • $\begingroup$ @YangWang I only said "might be difficult". We usually measure the running time in terms of the input length. If the output is much longer than the input, then that implies that the running time is trivially large. In your problem that doesn't seem to be the case after all. $\endgroup$ – Yuval Filmus Feb 19 '16 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.