12
$\begingroup$

I have a very generic question to ask. It is related to research. I'm interested in Graph theory. I have done a course in it. I have done some topics related to both graph theory as a point of view of doing it as a mathematics student and also studied some graph algorithms. I'm going for research internship in graph theory. But there is some glitch in my mind that I'm unable to fix about my real interest in graphs because of lack of proper distinctive ideas about the real difference in doing research in graph algorithm or doing graph theory as a mathematics student. I would like to know the following things:

  1. What is the real difference in doing graph theory as a mathematics student or doing graph algorithms? Do both of them have some real difference?
  2. Can someone tell me some good source for getting research papers on graph theory and graph algorithms.
  3. Is it good to start doing graphs as a mathematics student?

I don't know if it is a right place to put forward such kind of problems. Please let me know if it doesn't fit here.

$\endgroup$
  • $\begingroup$ lots of overlap & meshing more all the time with eg big data & it doesnt have to be an "either-or". graph algorithms tend to be more applied/practical, graph theory tends to be more theoretical. graph theory is more about properties/proving theorems... its like asking the difference between CS/math... which do you have more of an affinity for? another point is that some graph theory is theoretically significant yet impractical or "nonconstructive" and cant be used for algorithms or is an open question if any algorithms exist... also a neat area of strong overlap is "graph complexity"... $\endgroup$ – vzn May 19 '14 at 1:09
9
$\begingroup$

Question 1

I would say that the two areas are definitely not identical, however there is a huge overlap. Partly it depends on where you draw some very fuzzy lines. Let's start with:

  • Graph Theory is about the properties of graphs as mathematical objects
  • Graph Algorithms as an area of research is about solving computational problems that are represented using graphs.

Of course graph theory is unsurprisingly very useful in developing graph algorithms, and graph algorithms can answer questions in graph theory. Indeed, as you have obviously noticed, many problems in Graph Theory can be cast as computational problems, and answered by giving an algorithm (in a sense this is an aspect of the Curry-Howard Correspondence), so especially at the introductory level, there is little more than the style of presentation that separates them.

Just to make things even more confusing, most researchers in one field have at least some interest and experience in the other, but there are a couple of points where we can draw certain lines of distinction:

  • Graph theory (as a field) will happily deal with infinite graphs, which are not so interesting from an algorithmic perspective.
  • Graph theorists will tend to be more interested in existential statements ("the chromatic number of a class of graphs is at most blah"), whereas graph algorithms people will be looking for the best algorithm to solve a problem ("how do we compute the actual value of the chromatic number as quickly as possible?").
  • Graph algorithms includes/overlaps with the application and tailoring of graph algorithms to solve problems that aren't really about graphs (e.g. developing a good algorithm to cluster protein interaction networks), which a graph theorist would be uninterested in (at least as a graph theorist).

Question 2

If you have access to university subscriptions or similar (this is no way exhaustive):

To muddy things further, many of these include examples of both pure graph theory and graph algorithms.

A couple of lists for further exploration:

There is the arXiv preprint server, which has preprint versions of research papers, but again, you'll have to spend a small amount of time to explore and find something you want (it's more set up for finding a paper you already know is there).

Question 3

This question cannot really be answered objectively. It depends entirely on things that you have no way of knowing (i.e. the future), and I have no way of knowing (how good the people are at your university, what opportunities you will gain or lose by taking that internship).

If you want my subjective general opinion, I would say yes. Graph theory is an important part of mathematics and computer science (I personally contend they're not different things anyway), and versatility and breadth of knowledge are important characteristics of a good researcher, even if you later decide you have no intention of being a graph theorist - it's not going to stop you from being able to do complex analysis or topology.

Again, this is about whether an arbitrary student would benefit from doing work in graphs (algorithms or theory) - you personally may be in a particular situation where it would not be beneficial, and we can't answer that here. For example, if taking the internship means that you don't get to do the internship in Category Theory that is actually the thing you want to do, then this could set you back. Early in a research career it is difficult to escape a particular path, without going back to step one. Later on, it's easier to transition, but for better or worse there's period effectively like apprenticeship where you can't easily jump to any job you're interested in, but that's a question for Academia.SE.

$\endgroup$
  • $\begingroup$ "Graph Algorithms as an area of research is about solving computational problems that are represented using graphs." Or just computational problems on graphs. The graph doesn't have to represent anything for algorithms on it to count as graph algorithms. $\endgroup$ – David Richerby Oct 6 '15 at 19:00

Your Answer

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

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