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

-1
votes
1answer
19 views

Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1?

Let G be k-reguler bipartite graph of degree at least 2, for all v belong to V(G) prove that k(G-v) is connected?
-1
votes
0answers
16 views
22
votes
1answer
820 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 ...
1
vote
1answer
60 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by: $$ w(U,U^C) := ...
0
votes
0answers
25 views

How to find maxflow with minimum number of edges?

I am struggling with the flowing problem: You are given a source s and a sink t and a biparted graph G. All vertices {v} from the left half are connected to the source s with given capacity C[v]. ...
1
vote
1answer
31 views

Finding one face in planar graph

Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle. How do we find ...
4
votes
0answers
27 views

find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
1
vote
1answer
26 views

TSP Edge Removal

Are there any papers/algorithms for finding edges in a graph that can be removed with affecting the graph's optimal TSP tour length? For instance, in a Euclidean TSP instance, many edges could be ...
3
votes
0answers
81 views
+100

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
3
votes
0answers
12 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
1
vote
1answer
74 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of ...
5
votes
2answers
62 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
1
vote
1answer
97 views

When is the output of shortest path $\subset$ MST?

I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like: The shortest path $B ...
-5
votes
1answer
71 views

Proving a problem is in P? [on hold]

Problem: A square in an undirected graph is a cycle of length 4, i.e. four vertices that form a cycle. Show that the problem: ...
1
vote
2answers
37 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.
0
votes
0answers
7 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
4
votes
1answer
67 views

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible. The only way I found is generating the first graph using the Havel-Hakimi ...
1
vote
1answer
44 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
12
votes
3answers
5k views

Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": ...
1
vote
1answer
36 views

What does a ball of center v and radius r with at most r hops away mean?

I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set: $$ B(v, r) = \{ x \in ...
0
votes
1answer
30 views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
-1
votes
0answers
14 views
6
votes
0answers
121 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
0
votes
1answer
26 views

Can an independent set (of vertices) be a vertex cover as well?

I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set: So, to clarify, am I right to say that the nodes in red are both (i) a ...
0
votes
1answer
22 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
4
votes
1answer
65 views

Decomposing the n-cube into vertex-disjoint paths

I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be ...
0
votes
0answers
40 views

Find closed loops in an undirected graph given an adjacency list

I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of. For example ...
2
votes
2answers
123 views

Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
0
votes
1answer
19 views

Check Cycles- On adding an edge in DAG

Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be ...
1
vote
0answers
153 views

Finding all circuits in a graph

I'm trying to find out how many circuits exist in a graph $G$, given its adjacency matrix. Yet, the only thing I know is how to find out if there is a circuit in a graph $G(X,U)$ given a list of ...
2
votes
1answer
28 views

Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

I stumbled upon the following problem during my research. I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting ...
0
votes
1answer
76 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = ...
1
vote
1answer
56 views

Markov Chain Mixing Time of the Complete Graph

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn). We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically ...
4
votes
1answer
38 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to ...
1
vote
1answer
24 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
0
votes
2answers
43 views

Induced subgraph problem in trees

Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for ...
3
votes
1answer
80 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
12
votes
4answers
355 views

Dijkstra's algorithm on huge graphs

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to ...
1
vote
2answers
55 views

Which is more fundamental: key-value or subject-predicate-object?

There seems to be two approaches to store data in NoSQL databases: Key-Value - The Key is usually stored in a hash-table referencing a ...
3
votes
1answer
40 views

How to generate a degree sequence of a degree distribution

How to generate a degree sequence of a degree distribution that follows the power-law in which I know $N=10^2$ and $\gamma=2.5$? The degree distribution of power-law is $p_k \sim k^{-\gamma}$. I ...
2
votes
0answers
53 views

General Steiner Tree Variants

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all ...
2
votes
0answers
23 views

Maximum Weight Planarization of Size $n$ [duplicate]

Problem: Maximum Weight Planarization Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges. Find the subgraph with $n$ nodes (but possibly removing edges ...
3
votes
0answers
122 views

Online bipartite edge-cover problem with requirements

I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following ...
1
vote
1answer
322 views

Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
3
votes
1answer
9k views

Reducing Clique to Independent Set

The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) ...
2
votes
1answer
46 views

Is the unweighted vertex cover problem equivalent to its weighted version?

Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} ...
7
votes
2answers
391 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
1
vote
1answer
33 views

Residual Graph in Maximum Flow

I am reading about the Maximum Flow Problem Here. I could not understand the initiation behind the Residual Graph. Why we are considering a back edge while calculating the flow. Can anyone help me in ...
0
votes
0answers
16 views

Linear and Non-linear data set in K-means algorithm

The site K-means says that the algorithm fails for a non-linear data set. What do you mean by a non-linear data set in clustering algorithms? How different is it from a linear-data set?