Stack Exchange Network

Stack Exchange network consists of 174 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 [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.

0
votes
0answers
12 views

Why irreducibility is an important concept in Flow Graphs?

Here is a definition of reducible flow graphs : A flow graph is reducible if every retreating edge in any DFST for that flow graph is a back edge. And the reasons why we care about ...
0
votes
1answer
30 views

Is TSP a more detailed form of the “Set Inclusion” question?

Set Inclusion GIVEN: set of cards, some with blue backs, and each with a positive, integer face value. QUESTION: Are there any [blue-backed cards] with a [face value <= L]? 2 independent ...
1
vote
1answer
38 views

Reducing a graph without changing its chromatic number

Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name? Take this cactus graph as an example (although my question is about an ...
1
vote
1answer
38 views

How to perform local search to find maximal induced subgraphs?

I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example. What I mean by local ...
1
vote
0answers
26 views

Alternatives to directly connected networks for representing frequently-updated graphs

What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated,...
4
votes
2answers
63 views

When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then ...
0
votes
0answers
17 views

Finding disjoint paths between any number of cell pair marked in nXn matrix

What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix? We will say two paths will not intersect if there there is no cell common between any two ...
1
vote
0answers
20 views

Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
0
votes
0answers
11 views

How to identify the final set of “contours” when combining multiple primitive contours

This problem is in relation to how fonts work. Say you have a "glyph" that is composed of of these 5 "contours", or enclosed loops. On their own, each of them is a unified whole. The easiest thing we ...
2
votes
0answers
17 views

Complementary of graph invariant

Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
-1
votes
0answers
42 views

Reduction from “restricted-3-partition” to “k-graph-partition”

I need a reduction from “Restricted-3-partition” to “k-graph-partition” that can be done in polynomial time, but I have absolutely no clue how to start this off. Can anyone help me out with an ...
3
votes
1answer
102 views

Optimal dividing of K people into N groups

A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or ...
0
votes
3answers
61 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
0
votes
0answers
31 views

Can the Chinese Postman Problem be solved with the Traveling Salesman Problem?

Multiple people suggest that the Chinese Postman Problem (also referred to as the Route Inspection Problem) of a graph G can be solved by applying the Traveling Salesman Problem to its line graph L(G)....
1
vote
1answer
29 views

Delete a node with 2 children in a binary search tree

Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion. Case 1: The node is a ...
0
votes
0answers
19 views

Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
3
votes
0answers
171 views

How to select a loop nesting trees for irreducible loops?

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
1
vote
0answers
65 views

Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges

A bipartite graph $G$ and an integer $K$ is given. I want to decompose $G$ into $K$ complete bipartite graphs by adding the smallest number of edges. Below is an example of decomposition when $K=2$. ...
0
votes
0answers
13 views

Is this function injective or surjective? [closed]

I have a function with an ordered paid as an argument: Z × Z → Z given by f(m, n) = m − n − 1 I thought that it is surjective as m and n would be many combinations of values mapping to every value ...
1
vote
1answer
30 views

Generating a random minimum spanning tree

I am tring to find the simplest method of generating a random minimum spanning tree. My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a ...
1
vote
0answers
23 views

Solving a pursuit-evasion game

Let's say we have a simple connected and undirected graph $G(V,E)$. The game is played with two players. For each game, player A starts at a node $t$, and player B at a node $v$. There is also a node $...
1
vote
1answer
22 views

Word ladder problem for words with different length

Is there some one who know any algorithm for word ladder problem with words of different length? Actually we have some strings with same length and some strings with one length longer but not from ...
0
votes
0answers
18 views

Counting chords intersections in a circle

The problem is: Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ ...
1
vote
0answers
22 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?
4
votes
3answers
235 views

Hard connected instances for Weisfeiler-Lehman test of isomorphism

There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm. However, one of these graphs is disconnected. So what are the instances ...
1
vote
0answers
14 views

Relation between deficiency and color class parity of graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
2
votes
0answers
30 views

Method to calculate score in a go game

I'm currently programming a go game, and I'm struggling with some aspect of the game, especially how to handle the end game, how to count points and how to detect dead stones ? I thought of doing a ...
1
vote
2answers
39 views

Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
0
votes
1answer
33 views

Graph Edit Distance

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition. Link: https://www.springer.com/cda/content/document/...
0
votes
0answers
22 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
0
votes
2answers
56 views

Time Complexity and graphs

I'm learning graphs these days and need to clear few doubts- Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1). What is the ...
2
votes
1answer
20 views

Resource Reservation: No Greedy Approach?

I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only ...
2
votes
1answer
74 views

What is the point of traversing a binary tree in preoder, inorder or postorder?

Why not use breadh-first like in any other graph ?
2
votes
1answer
72 views

Finding the longest path in an undirected node-weighted tree

I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the ...
1
vote
1answer
120 views

How to reduce 3-COLOR to 42-COLOR?

The requirement is that two adjacent vertices have different colors, and max. 42 colors. I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes ...
2
votes
1answer
39 views

Shortest path with a start vertex that touches all nodes at least once with repeats allowed

I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
1
vote
1answer
44 views

Distinct Minimum Weight Spanning Trees

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider ...
1
vote
1answer
25 views

Multiple rounds of bipartite matching problem

I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with ...
0
votes
0answers
26 views

Repeated subgraph isomorphism query for single-edge addition for bounded degree graphs

I have a source undirected colored graph $G$ and a base query graph $g$. I know $g$ is subisomorphic to $G$ and now I want to identify which edges I can add to $g$ to preserve subisomorphism. That is, ...
1
vote
3answers
51 views

Is this definition of a “complete graph” correct?

Is it correct to say that: "A complete graph is a graph in which each vertex is connected to all other vertices in the graph" That's how I always thought about it, the official definition is ...
-1
votes
2answers
40 views

Solve this integer program (problem: Travelling salesman problem)

How do one solve the following integer program? $$ \begin{align*} \text{minimize} \quad &\sum_{(i,j) \in E} d_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j \in V} x_{ij} = 2 \;\; \forall i ...
2
votes
1answer
504 views

Direct edges of undirected graph so that all indegrees are even

Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even. For example, consider ...
1
vote
1answer
35 views

Graph theory: determining maximum number of edges

Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful ...
1
vote
0answers
42 views

Enumerate all re-convergent paths in a digraph (with cycles)

I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, ...
1
vote
0answers
100 views

Proving there is no polynomial algorithm for independent set

I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
2
votes
2answers
48 views

Prove that the number of edges is at least twice the number of vertices

I need to prove that In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices. I already know that $\deg(n) = ...
0
votes
0answers
24 views

Finding shortest cycle in graph with positive weights

Given a graph G, with all positive weights, find the shortest cycle length in O(V^3) My idea is, negate al the edges, apply floyd-warshall algorithm and then for all $i$, find the largest $M[i][i]$ ...
3
votes
1answer
42 views

Strongly connected orientations of undirected graphs

I'm trying to prove the following. There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge. (An orientation of an undirected ...
3
votes
1answer
42 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
0
votes
2answers
32 views

MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ...