0
$\begingroup$

I want to know if there exist a algorithm to efficiently compute the number of odd vertex in an undirected graph?

A graph vertex in a graph is said to be an odd vertex if its vertex degree is odd, degree of a graph vertex v of a graph G is the number of graph edges which touch vertex v.

This post conclusion seems to be that this is #P-hard but this doesn't seem that hard to me but I don't have any direct argument against it ,that's why I want to know if there exist a reduction from this problem to some #P-complete problem or is it polynomially solvable?

What I didn't understand from linked post is why counting odd vertex is related to counting number of satisfiable instance of SAT.

Also counting the number of odd vertex seems to be solvable in linear time ,all we'd have to do is check each vertex to see if they have a odd degree if yes add 1 to the odd_vertex_number variable ,this way we can solve it in linear time ,that's why I can't understand why this is #P-hard?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

You are indeed correct : Given a graph $G$ in the form of its adjacency matrix, you can find all the odd degree vertices in polynomial time of the number of vertices.

The post that you mention does something different. Notice that you may decide to mention the graph in some form other than the adjacency matrix. Assuming the graph has $n$ vertices, you only need $\log n$ bits to state the number of vertices. However now that you want to state the edges, you do not do the adjacency matrix representation (this representation would take up $n^2$ bits). Instead you decide to create a circuit of $\log n$ size. The circuit's job is to take as input a vertex and output its neighbours. Now notice that you have given the entire $n$ vertex graph in $O(\log n)$ bits. Not all graphs may be represented like this, but given a graph in this format you now want to find odd degree vertices. Since the input size is $O(\log n)$, you want to make the computation in polynomial of $O(\log n)$ and now your algorithm is exponential in this setting.

Improve this answer
$\endgroup$
6
  • $\begingroup$ But even if we use differnet representation for a graph, information about the graph will remain same right?Like the vertex that can be seen as odd in adjancey matrix representation would still be odd in the circuit representation ,can't we just use the adjancey matrix version and calculate the number of odd vertex then? $\endgroup$
    – Anuj
    Feb 8 at 5:04
  • $\begingroup$ Ok suppose I give you a number $n$ and ask you if it is prime. In order to give you the number I need $\log n$ bits right? Now you can try all the numbers less than $n$ and see that if they are a factor or not. Since there are $n-2$ numbers below $n$, you will have to divide $O(n)$ times. This is exponential in the input size. However if I had given you the number $n$ as $11111.....1$ ($n$ many $1$'s) then the the input size is $n$ and the algorithm would have been poly in input size. It is similar here. You can't write the adjacency matrix, since the size of matrix is exp in input size. $\endgroup$
    – User Not Found
    Feb 8 at 6:12
  • $\begingroup$ It is like saying, I will accept SAT inputs as a table : The table will give me the value of the SAT expression ($0$ or $1$) for a given configuration of variables. In this scenario, SAT is polynomial time in input size because the SAT is mentioned in an exponential sized input. $\endgroup$
    – User Not Found
    Feb 8 at 6:16
  • $\begingroup$ so its like that the problem we need to represent would be exponential with resprect to input if we had chosen adjancey matrix because it capture more information about the graph which in turn makes it easier for us to solve the problem but beqacuse its exponential with respect to inputs its inefficient ,but we can represent the same problem as circuit which is polynomial with respect to the inputs but because it doesn't contain that much information about graph like adjacey matrxi it makes it harder for us to solve the same problem in circuit representation? $\endgroup$
    – Anuj
    Feb 8 at 6:25
  • $\begingroup$ Very good, I was not sure if I explained in a nice way. You seem to have understood. It is a fairly non-intuitive (or weird) concept. The prime number testing problem was there in my exams once and I had messed up, that is how I learnt it. $\endgroup$
    – User Not Found
    Feb 8 at 6:30

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.