Questions tagged [graph-theory]

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

3
votes
0answers
15 views

Normal colorings of cubic graphs (part 1)

Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or ...
2
votes
0answers
62 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
0
votes
1answer
29 views

Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
-1
votes
0answers
39 views

Longest simple circuit and P=NP relation

Given the following function: $$\:f\left(G,v\right)\:=\:size\:of\:the\:longest\:simple\:circuit\:in\:a\:directed\:graph\:G\:that\:contains\:v$$ Output: Function returns a natural number or 0, which ...
0
votes
0answers
23 views

Efficient algorithm to prune a graph [on hold]

I'm faced to a problem I don't know the name, and for which I'm searching an efficient algorithm. From two list of nodes (without shared elements), the aim is to remove edges between element of the ...
2
votes
1answer
23 views

Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. Input: An undirected graph $G=(V,E)$, $s,t \in V$. ...
2
votes
0answers
45 views

Is there an algorithm to add edges to a DAG to make it strongly connected with minimum cost?

I have a weighted DAG and a function computing the weight of edges that is not connected in the DAG. The weight of u to v equals ...
1
vote
1answer
19 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
3
votes
0answers
61 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
2
votes
1answer
22 views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
1
vote
0answers
57 views

divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the ...
2
votes
1answer
23 views

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems: $CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components} $E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
2
votes
1answer
22 views

Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
1
vote
0answers
12 views

Log-space reduction from $USTCON$

Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
3
votes
0answers
17 views

Random paths from one point to another going through all the cells of a square grid

I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it. My problem is about a square grid of size <...
1
vote
1answer
42 views

Decision problem - vertex with path to all other vertcies

Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies. I am able to place this problem in NL, similarly to the strongly-...
0
votes
0answers
33 views

Clique of constant size

It is well known that Clique is a $NP$-Complete problem, But given some constant value $K$, finding whether a graph $G$ has a clique of size $K$, is always a log-space ($L$) class problem?
2
votes
2answers
34 views

How to verify Hamilton-Path in log-space?

Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all ...
1
vote
1answer
15 views

$stCON$ with path of length $≥ n/2$

The following problem seems very similar to the $stCON$ decision problem: {$G, s,t | G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$, there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/...
2
votes
1answer
29 views

Transitive Closure vs Reachability in Graphs

I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph <...
4
votes
1answer
29 views

Graph ordering with smallest max vertex “discrepancy”

Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers. Define the cost of an ordering ...
2
votes
1answer
31 views

What algorithm will tell us how to divide-up a round robin tournament into rounds?

We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly ...
0
votes
0answers
21 views

Single source shortest paths with even path [duplicate]

Given directed graph with non negative weights and vertex s. I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
1
vote
1answer
42 views

Calculate probabilty to escape the maze

I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement The Frog is in an two-dimensional maze represented as a table. ...
2
votes
1answer
114 views

Proof that shortest path with negative cycles is NP hard

I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is ...
5
votes
2answers
134 views

Finding row wise sum of transpose of hv-convex binary matrix

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m). ...
2
votes
0answers
16 views

Correctness of Karger's min-cut Algorithm

tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
1
vote
1answer
37 views

Finding a cycle in a graph with the biggest value (the sum of all edges)

I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred ...
0
votes
1answer
27 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
3
votes
1answer
46 views

Cannibals missionaries problem - solving usings graphs

I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other ...
2
votes
3answers
51 views

Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
3
votes
1answer
50 views

Showing Cycle is NL-complete?

Consider the following decision problem : Cycle: Given a directed graph G, does G contains a directed cycle? It is very clear why Cycle belongs to NL. My question is - how to show Cycle is ...
9
votes
3answers
1k views

Intuition behind eigenvalues of an adjacency matrix

I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a ...
3
votes
1answer
82 views

NP-completeness of Induced disjoint paths

In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs. Our problem ...
4
votes
2answers
394 views

NL - iterating all edges of a graph in log space

Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because ...
0
votes
0answers
9 views

Online bipartite matching problem for task assignment

I have $n$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current ...
1
vote
1answer
30 views

Reduction from minimum dominating set to the set cover

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem. For example to find the MDS of the graph G: We can create an instance of the Set Cover problem by: ...
3
votes
2answers
43 views

Graphs of maximum degree three

I'm learning an algorithm for graphs of maximum degree three. My question is: should the graph of that type have at least one vertex with degree three. For example if the maximum degree of some ...
1
vote
0answers
10 views

complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
1
vote
1answer
31 views

Variant of stCON

Consider the following variation on stCON desicion problem: Given a directed graph G, decide whether for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. ...
1
vote
0answers
21 views

How to Track Connected Components in a Graph when Deleting Nodes

Suppose you have a graph G, and you want to support the following operations: addNode(Node n) addEdge(Node n1, Node n2) ...
0
votes
2answers
21 views

Spanning trees on disconnected graphs

Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?
1
vote
0answers
65 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
1
vote
1answer
28 views

Determining the number of walks between two vertices in a graph

Given a graph G and a set of vertices $(v_1, v_2)$. How can you determine whether there is $\textit{one}$ unique walk between $v_1$ and $v_2$?
0
votes
0answers
44 views

Intuition for the convergence of the distance vector routing protocols

What is an intuitive way to think about the convergence of the distance vector routing algorithm? According to Wikipedia: Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–...
0
votes
1answer
43 views

The cheapest path in the graph [duplicate]

I am supposed to decide, if the statement is true or false and use arguments for my answer. In every weighted n-vertices graphs: with no negative weighted edges, with n>10, in which every weighted ...
3
votes
2answers
75 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
2
votes
1answer
86 views

Subtree with minimum sum of nodes' costs

Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
2
votes
2answers
34 views

Uniqueness of minimum spanning tree

If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?
-1
votes
1answer
40 views

Doubt in vertex connectivity less than edge connectivity [closed]

Sir i recently started graph theory. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in 2nd part of proof when ...