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-algorithms]

Algorithms on graphs, excluding heuristics.

1
vote
0answers
172 views

Algorithms for finding all cliques of a given degree in a graph

Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$. Bron-Kerbosch algorithm gives all maximal ...
6
votes
0answers
96 views

Optimal polynomial time algorithm to determine if a random graph is $k$-colorable

Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
3
votes
0answers
623 views

Is there a better than brute-force solution to the shortest simple path problem?

Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex ...
15
votes
2answers
514 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
0
votes
0answers
75 views

Looking for a list of algorithms that are more efficient for an outerplanar graph than for an arbitrary graph

I'm Looking for a list of algorithms that are more efficient for an outerplanar graph than for an arbitrary graph. I found only the following: ...
6
votes
0answers
79 views

Finding almost minimum cycle

Given an undirected unweighted graph, the almost minimum cycle is defined as the cycle whose length is greater than that of a minimum cycle by at most one. Itai and Rodeh in a seminal paper in 1978 ...
8
votes
0answers
212 views

Embedding a graph with specified edge lengths in d-dimensional space

Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have ...
0
votes
0answers
113 views

Computing mTSP in a k-complete weighted graph

Short Story: I have a weighted digraph and I need to perform a multi TSP on it. The digraph that i'm working on have the following restrictions: It is a complete digraph, so for every node p and q ...
2
votes
0answers
81 views

What can i learn about a graph about which only certain properties are known [closed]

1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts? The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable, The degree of each ...
5
votes
1answer
135 views

Hardness of Subgraph isomorphism problem for sparse pattern graph

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
2
votes
0answers
146 views

Computational Complexity of cycle double cover

Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
2
votes
0answers
52 views

Examples of “Sandpile” TSP Instances

This question is closely related to this MO question. I would like to know, whether any (planar Euclidean) TSP instances are known, that exhibit avalanche effects similar to those ecountered in ...
3
votes
0answers
170 views

zero-sum path problem on a digraph

Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the ...
7
votes
3answers
495 views

Hard problems for bounded vertex cover

We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
-2
votes
1answer
196 views

questions on implications Babais quasi P time graph isomorphism result

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs. based on the proof, does this mean now that if Johnson ...
3
votes
1answer
160 views

Efficient enumeration of the reachable leaves of nodes in a polytree

A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart. Given a polytree $T$ and a node $...
5
votes
0answers
123 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
-2
votes
1answer
171 views

Bounded 0/1-knapsack with dependency constraints without limit

Consider a set of items, weighted with real numbers / costs. You are supposed to select a subset maximizing the sum of the weights of the selected items. But the following contraints must be observed: ...
2
votes
1answer
201 views

Partition refinement in transition state systems (bisimulation contraction)

I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ...
0
votes
0answers
207 views

A linear time algorithm for the all pair longest paths on a special kind of trees

Consider an edge-weighted graph $G=(V,E_G)$, a spanning tree $T=(V,E_T)$ of $G$, and a simple path $P$ in the tree that connects a leaf $\ell\in T$ to the root $r\in T$. A pebble starts in the leaf $\...
3
votes
3answers
161 views

Approaches for Theoretical Analysis of Estimates of Probability Distributions

Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
9
votes
2answers
210 views

Nonstandard dual parametrization of graph problems

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when ...
-1
votes
1answer
666 views

Reachability on DAG (best-known algorithm)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, ...
0
votes
1answer
85 views

Number of bounded minimum vertex covers

Minimum Vertex Cover problem Input: $G=(V,E)$ and Parameter $k$ Output: Decide whether there exists minimum vertex cover of size at most $k$. Question:- Can we bound the number of minimum vertex ...
4
votes
1answer
109 views

Shortest cycle separator for biconnected planar graphs

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is ...
3
votes
1answer
319 views

Max weight k-clique

Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however ...
4
votes
1answer
126 views

Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known. The ...
2
votes
1answer
215 views

Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in ...
10
votes
0answers
281 views

Triangle arrangement problem

Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
5
votes
0answers
127 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete?...
1
vote
1answer
135 views

Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $...
1
vote
1answer
853 views

Longest path from every vertex in a tournament

I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path ...
1
vote
0answers
1k views

Fastest Algorithm for the Minimum Edge Covering Problem

Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints: G' must include all the ...
3
votes
1answer
203 views

Finding a graph that minimizes the number of nodes for a given number of paths

There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting ...
1
vote
0answers
95 views

Detecting bridges in Hypergraph S-t Reachability

Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
8
votes
2answers
569 views

Dichotomy of the spectra of directed graphs

Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known: It is known that a directed graph $G = (V,E)$ has an adjacency ...
1
vote
0answers
91 views

Concentration Bounds for functions of matrices

This is a question about properties of large directed graphs which are preserved when we randomly sample edges. Imagine I have an infinite sequence of positively weighted directed graphs. The ...
2
votes
1answer
237 views

Are there any results on the following “generalized matching” problems?

Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic ...
7
votes
2answers
176 views

Something-Treewidth Property

Let $s$ be a graph parameter (ex. diameter, domination number, etc) A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph $G\in \mathcal{...
10
votes
3answers
683 views

Shortest distance problem with length as functions of time

Motivation The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two ...
3
votes
2answers
351 views

Does the problem “partition a vertex-weighted graph into $k$ balanced connected parts” have a standard name?

Consider the following problem: Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
4
votes
1answer
142 views

Bidirectional A*: is an update of the distance estimation feasible while searching?

The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal. The ...
0
votes
1answer
122 views

The number of edges in the ith shortest path in a directed graph

$G$ - directed graph, $n$ - count of nodes According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges. Anybody can explain how this estimate is ...
-5
votes
2answers
1k views

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
6
votes
2answers
369 views

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
1
vote
1answer
250 views

Triangular Mesh Reordering - Huddling Triangles

I am given a 3D model represented by its outside surface as a triangular mesh (hollow inside). The model is mostly 2-manifold, so that each triangle edge is shared by exactly 2 triangles. This, ...
2
votes
1answer
150 views

Maximum cardinality subgraphs meeting a Jaccard overlap threshold

Consider two undirected connected graphs $G_0$ and $G_1$. The graphs are subgraphs of a given connected graph $G$ and share at least one node. I want to find two subgraphs $G_0'\subseteq G_0$ and $...
0
votes
0answers
37 views

Existing of Single Center Graph construction Algorithm

I want to construct a graph $G$ with $n$ number of nodes and $m$ number of edges. The construction should leads to a graph with single/double center. But not more than that. If we take $m=n-1$, then ...
1
vote
2answers
206 views

Reduction from independent set in hypergraphs to independent set in graphs

Let me introduce my notations. IS-H : Input : an hypergraph $G=(V,H)$, an integer $k$ Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
1
vote
0answers
104 views

algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...