Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

32
votes
6answers
12k views

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
19
votes
1answer
4k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
17
votes
2answers
371 views

Finding at least two paths of same length in a directed graph

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...
17
votes
1answer
588 views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
16
votes
1answer
387 views

Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
13
votes
1answer
337 views

How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
12
votes
3answers
4k views

The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
11
votes
2answers
1k views

Why we do isomorphism, automorphism and homomorphism?

What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and why we do isomorphism, automorphism and homomorphism ?
11
votes
2answers
3k views

Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
11
votes
1answer
625 views

How many max heaps are there?

How many different max-heaps can I form using a list of $n$ integers. Example: list [1,2,3,4] and max-heap is 4 3 2 1 or ...
11
votes
3answers
3k views

Finding the minimum cut of an undirected graph

Here's a question from a past exam I'm trying to solve: For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that ...
11
votes
2answers
210 views

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ ...
11
votes
1answer
396 views

Proving that directed graph diagnosis is NP-hard

I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and ...
11
votes
2answers
234 views

How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
11
votes
1answer
262 views

Minimal Spanning Tree With Double Weight Parameters

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
11
votes
0answers
225 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
10
votes
4answers
336 views

Is this finite graph problem decidable? What factors make a problem decidable?

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
10
votes
2answers
3k views

Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found this in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": Problem: ...
10
votes
2answers
503 views

Chromatic polynomial of a square

Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available.. That is there are ...
10
votes
1answer
149 views

Number of Hamiltonian cycles on a Sierpiński graph

I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
10
votes
2answers
1k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...
10
votes
1answer
177 views

Transforming an arbitrary cover into a vertex cover

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
10
votes
1answer
274 views

Longest cycle contained in two cycles

Is the following problem NP-complete? (I assume yes). Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not ...
9
votes
1answer
210 views

$O(n^{k-1}$) algorithm for K-clique problem

Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is ...
9
votes
1answer
2k views

Is the k-clique problem NP-complete?

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete: Cliques have also been ...
9
votes
3answers
139 views

Wiring Length Minimization

My Problem is like this: I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where ...
9
votes
3answers
1k views

Graph Has Two / Three Different Minimal Spanning Trees?

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
9
votes
1answer
210 views

Pebbling Problem

Pebbling is a solitaire game played on an undirected graph $G$ , where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex $v$ and adding ...
9
votes
1answer
314 views

Number of clique in random graphs

There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
9
votes
2answers
125 views

Hard computational problem on special class of bipartite graphs

I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known ...
9
votes
1answer
342 views

Assignment problem for multiple days

I have a problem that can be reduced to an assignment problem. (In a previous question i found out how to do that.) Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost ...
9
votes
2answers
666 views

NP-Completeness of a Graph Coloring Problem

Alternative Formulation I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to ...
9
votes
1answer
121 views

Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ ...
9
votes
0answers
83 views

Finding an st-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path $P$ which minimizes ...
8
votes
2answers
246 views

Size of Maximum Matching in Bipartite Graph

Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?
8
votes
5answers
546 views

Standard or Top Text on Applied Graph Theory

I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the ...
8
votes
2answers
283 views

Reconstructing Graphs from Degree Distribution

Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph ...
8
votes
1answer
1k views

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
8
votes
1answer
159 views

Finding the largest 3-clique-free induced subgraph

Consider this problem: Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that: $G'$ is an induced subgraph of $G$ $G'$ has no 3-cliques $|V'|$ is maximal So the ...
8
votes
2answers
877 views

What is the average height of a binary tree?

Is there any formal definition about the average height of a binary tree? I have a tutorial question about finding the average height of a binary tree using the following two methods: The natural ...
8
votes
1answer
53 views

Is the per-vertex error over a PageRank iteration monotonically decreasing?

It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge. However, is the same ...
7
votes
4answers
152 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
7
votes
4answers
196 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
7
votes
5answers
193 views

Team construction in tri-partite graph

The government wants to create a team with one alchemist, one builder, and one computer-scientist. In order to have good cooperation, it is important that the 3 team-members like each other. ...
7
votes
2answers
3k views

Prove that every two longest paths have at least one vertex in common

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common. I think that that common vertex ...
7
votes
3answers
245 views

Unique path in a directed graph

I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...
7
votes
2answers
56 views

Compute relational composition in $O(|E||V|)$

Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs. Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in ...
7
votes
2answers
76 views

Low-degree nodes in sparse graphs

Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one. I have tried to solve this ...
7
votes
1answer
227 views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
7
votes
1answer
131 views

Approximation algorithm for Feedback Arc Set

Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set. I want to find out about is ...