Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

2
votes
1answer
93 views

Does a Vertex Cover exist?

This should be a simple question, but I am a little bit confused. A proof on page 556 of Algorithm Design says: "Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $...
3
votes
2answers
96 views

Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
2
votes
1answer
43 views

Are you allowed to change the specifications of a problem when doing reductions?

I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
1
vote
1answer
81 views

Greedy algorithm to find Minimum Dominating Set in a tree

Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
1answer
20 views

Color a graph using k colors, k>4, with the most equal distribution of colors

Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors. Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, ...
1
vote
3answers
40 views

Intuitive proof for a tree with n nodes, has n-1 edges

I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
0
votes
1answer
21 views

Minimum perfect matching with uneven vertices?

Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?
1
vote
1answer
103 views

Need help to come up with definitive proofs with regard to Planar Graphs

I was working through a few problem sets and came across this question Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle ...
1
vote
0answers
13 views

Matrix represents weighted graph

In a question I've been given a 5x5 matrix that I'm told represents a weighted graph, and no other information. Here is an example: 0 4 5 2 2 3 0 3 3 1 1 3 0 5 2 2 4 4 0 2 2 3 2 5 0 My question is, ...
2
votes
1answer
119 views

Directed HAM Cycles with Additional Constraints to SAT

The $n$ dimensional hypercube $Q_n$ is a graph that has a vertex $v_s$ for each string $s \in \{0, 1\}^n$ and an edge between two vertices $v_s$ and $v_t$ if and only if the Hamming distance between $...
2
votes
1answer
36 views

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
2
votes
2answers
116 views

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance) $\alpha$ denotes the start and end vertex of ...
0
votes
1answer
63 views

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

What is the complexity of this problem EULERIAN ARC REVERSAL Input: a directed graph $G(V,A)$ and an integer $k$ Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
1
vote
0answers
51 views

Graph with two classes of nodes A and B: densest subgraph with same node classes cardinality

I'm searching (without results) a problem that can be reduced to finding the densest subgraph with the same cardinality between two classes of nodes. Consider a graph with nodes of class A and nodes ...
3
votes
1answer
60 views

Algorithm for minimizing the number of “inversions” in a graph

Given the following graph: With the assumptions below: A node on the left is linked to several nodes on the right Nodes on the right are paired together: one is black, one is white Each pair of ...
4
votes
1answer
19 views

In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs. I am confused about the definition of an $S_3$ graph....
1
vote
1answer
65 views

Behaviour of Dijkstra in Case of Negative Edge Weight [duplicate]

I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss. For the given below graph What should be the Cost to reach Node G from Source Vertex ...
0
votes
1answer
43 views

Cost of the MST of the graph [closed]

Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated! Although the picture shows a directed graph, please treat it as ...
0
votes
1answer
66 views

Deleting edges such that largest connected component has at most $n/4$ nodes

Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges. Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific ...
1
vote
1answer
59 views

proving correctness of algorithm about graphs with DFS

I need to prove/disprove the correctness of the following algorithm: Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that ...
1
vote
1answer
34 views

Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
2
votes
1answer
24 views

NP-Hard on Complete Graphs

I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
2
votes
1answer
40 views

minimum number of nodes that traverse all the graph

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
2
votes
0answers
73 views

Preferring forward edges to cross edges during graph DFS traversal

It's well known that depth-first search order of a graph is (usually) not unique, and multiple orders are possible depending on the order in which successors are processed for each node. Let's ...
1
vote
1answer
19 views

Chinese postman problem, but criteria = visit each vetex at least once

Chinese postman problem, but where the postman have to visit each vetex at least once. Is there a name for this problem? What is the ideal algorithm to solve this problem?
2
votes
1answer
37 views

Minimum cost node cut

I am interested in solving the following problem: Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph. Is there ...
1
vote
1answer
48 views

Checking if the graph provided by a distance matrix is a tree

I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily ...
2
votes
1answer
46 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
1
vote
1answer
41 views

proof that BFS remains total after adding edge to graph

I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$). The inductive proof consists in 2 cases: (i) Prove that $\rm{BFS}$$(u \in \...
0
votes
1answer
39 views

Do you >have< to define the upper and lower bound? (context: traveling salesman)

Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling ...
1
vote
2answers
90 views

Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution? (Thanks to many comments ...
1
vote
1answer
43 views

Calculate Shortest Path (Shortest Time) Through a Store in a Graph

There is an undirected graph and some of the vertices are said to be stores. Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores ...
6
votes
1answer
127 views

Does finding a cycle with $\log n$ length in $\text{P}$?

Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
1
vote
1answer
58 views

Post numbers in DFS tree of an undirected graph

How could you prove: An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the ...
1
vote
1answer
25 views

Complexity of two cycles which differ by $1$ in length

Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length. What is the complexity of this problem?
1
vote
0answers
23 views

Hungarian algorithm to search over all matching?

I am working on the following problem- "Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching." Please note that I like to search over all ...
1
vote
0answers
41 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
0
votes
1answer
13 views

Distribute to pairs with efficient algorithms

The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means ...
1
vote
2answers
172 views

Is there a name for this graph search strategy?

The standard implementation of breadth-first search looks like ...
3
votes
0answers
272 views

Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family

I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family Concretely: For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j ...
1
vote
1answer
44 views

Proof By Contradiction - Hamiltonian Paths and Cycles

Was hoping if anyone had any way to prove the following claim using proof by contradiction Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a ...
2
votes
2answers
36 views

Traversing a graph in finite time, maximizing utility

I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any ...
0
votes
1answer
274 views

Maxflow problem

I need help with the following practice problem on network flow: A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the ...
0
votes
1answer
18 views

There could not be an edge from u to v in a DAG, if w is before v in a topological order

I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
0
votes
1answer
28 views

How can we form a graph from this problem?

So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written ...
0
votes
2answers
42 views

Kosaraju with connections between SSCs (strongly connected components)

First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem. I have a graph which i condense into SSC (strongly connected components)...
1
vote
1answer
37 views

communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry ...
0
votes
2answers
33 views

Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
1
vote
1answer
18 views

Algorithm for commonalities across related objects

I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application. The problem is give the data below (two columns) ...
1
vote
1answer
90 views

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...