# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

861 questions
Filter by
Sorted by
Tagged with
13 views

### Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

(This question is inteneded for people who have heard of "Vertex Partitioning Problems" framework of Telle and Proskurowski. Others may dig in only if they are interested in practical algorithms for ...
81 views

### Minimum vertex cover and odd cycles

Suppose we have a graph G without odd cycles. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, ...
80 views

### How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to ...
74 views

### How to approach the “traveling salesman problem” with cost changing every time salesman reaches a new city

Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. Salesman can go to a different city only on weekends, all ...
54 views

### Reduction graph to planar bounded treewidth and bounded diameter graph

We got reduction graph to planar bounded treewidth graph, but this is unlikely to be true. Let $H$, the planarizing gadget, be planar graph with four distinguished vertices $u,u',v,v'$ on the outer ...
113 views

### Hardness of finding if a vertex lies on a simple directed path between two vertices

Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$? I found a couple of hardness ...
47 views

### Maximum subgraph problem with unknown complexity

Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem: Maximum $Q$-...
43 views

### Efficient game traversal of a DAG of 3-colorings

Let $X$ be a set of size $n$. Consider a game played on board $X$ by two players black and white. Starting with the empty board, each player chooses an empty spot to place a stone. Black moves ...
46 views

### Existence of graphs of every order related to Barnette’s conjecture

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
56 views

### Fast algorithm to find pair of triangles with a common edge in a complete graph

Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles ...
111 views

99 views

### Finding simple fixed length paths in directed graphs

Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?
73 views

Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\... 2answers 274 views ### How long does it take to find a short cycle in a random graph? Let$G \sim G(n, n^{-1/2})$be a random graph on$\approx n^{3/2}$edges. With very high probability,$G$has many$4$-cycles. Our goal is to output any one of these$4$-cycles as quickly as ... 2answers 183 views ### “Relatives” of the shortest path problem Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices$s,t$. Below are some path problems that are all of the following form: find an$s-t$path, such ... 0answers 129 views ### Enumerating Minimal (a,b) vertex separators in a DAG A vertex subset$S \subseteq V$is an$(a,b)$separator for nonadjacent vertices$a$and$b$if the removal of$S$from a graph$G$separates$a$and$b$into distinct connected components.$S$is a ... 1answer 110 views ### Relationship between$O(\log n)$(bounded) treewidth and H-minor-free What is the relationship between graphs which have$O(\log n)$treewidth and$\mathcal{H}$-minor-free graphs? Are graphs which have$O(\log n)$treewidth$\mathcal{H}$-minor-free? I know that graphs ... 1answer 215 views ### What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover? It is known that computing$(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a$(2 -\epsilon)$-approximation is hard. There is also a parameterized algorithm for ... 0answers 81 views ### Shortest s-t Path with a covering constraint Instance: an undirected graph$G=(V,E)$with edge-weights$w:E\to{\mathbb{R}}$; a source$s\in V$and a sink$t\in V$; a ground set$X=\{x_1, ..., x_k\}$, and for every$v\in V$a corresponding ... 1answer 233 views ### 3-coloring planar graphs in$O\left(3^{n^.5}\right)$? I was wondering if the task of searching for planar 3-colorings is known to be of complexity$O\left(c^{\sqrt{n}}\right)$or lower? This feels like it would be an intuitive consequence based from ... 0answers 74 views ### Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree I have encountered an interesting problem that I couldn't find any references to solve: Determine the smallest subset of nodes that need to be removed from an undirected graph to make it a tree. ... 0answers 45 views ### Matching of two weighted graphs allowing one-to-many mapping I am looking for a heuristic for a graph matching problem as follows. Given two graphs:$A$(consisting of nodes$a_i$) and$B$(consisting of nodes$b_i$). Typically the size of$B$is larger than ... 0answers 50 views ### Directed Acyclic Graph partition into minimum subgraphs with a constraint I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ... 0answers 77 views ### Common techniques for the acyclic orientation problem under some special constraint? An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ... 0answers 270 views ### Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model? Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a$\widetilde{O}(m+n)$time algorithm in ... 1answer 216 views ### Efficient graph isomorphism for similar graph queries Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one ... 0answers 21 views ### Connectivity with ordered adjacency list In the adjacency list model, a graph is described through lists that contain the neighbors of any node$i \in [n]$. A query is of the form "What is the$k$-th neighbor of node$i$?". BFS allows to ... 1answer 70 views ### Computing the existence of a path in a code execution graph I have a need for an algorithm which I can express as a reachability problem in a graph. Note that I'd appreciate any advices with respect to better wording this question. Also please tell me if this ... 0answers 68 views ### Unknown gaps in computation models I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ... 1answer 94 views ### finding maximum weight subgraph My graph is as follows: I need to find a maximum weight subgraph. The problem is as follows: There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ... 0answers 53 views ### Algorithms for Maximum weight connected subgraph in planar graphs I wonder what is known about the two following maximisation problems. Maximum weight connected subgraph : Input : A graph$G$, with weights$w_v\in \mathbb{R}$for each vertex$v \in V(G)$Output :... 1answer 56 views ### Min Cut with Vertices I have an undirected graph G with a set of vertices and edges. Each vertex has a weight w. Let's assume we have all vertices connected with some paths. I'm looking ... 0answers 56 views ### Graph automorphism with prescribed values Consider a graph$G$with vertices labeled$1,...,n$and edge weights$w_{ij}$. Recall an automorphism of G is a permutation$\sigma$of the vertex labels such that$w_{\sigma(i),\sigma(j)}=w_{ij}$... 1answer 166 views ### How many samples are needed to reconstruct a path? Consider an input set of vertices$V$and vertices$s,t\in V$. The goal is to learn some unknown shortest path from$s$to$t$; the set of edges of the graph is hidden at first and there may be ... 0answers 19 views ### The set of weight functions for which the assignment problem has non-trivial solutions The standard assignment problem is specified with a square matrix${\bf W}$of weights (values, costs): $$V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij},$$ where$\cal P$is a ... 1answer 76 views ### Finding a Hamiltonian cycle from perfect matching of a bipartite graph A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ... 3answers 299 views ### Is counting simple cycles in$P$for graphs of bounded tree width? Motivation: Determining if a graph has a Hamiltonian cycle is$NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ... 0answers 30 views ### Alternating Delivery Problem What is known about the complexity of the following problem: Suppose we have a complete bipartite graph$G(V,E)$with disjoint sets$C$and$T$. The candidate vertices, and the target vertices ... 0answers 81 views ### Minimum cut with nonlinear objective function Let$G$be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut$C\subseteq E(G)$, such that$|C|$is minimum. Let us generalize it the following way: let$f$be a ... 1answer 83 views ### Densest k subgraph problem for outerplanar graphs? The densest k subgraph problem aims to find a subgraph$H$of a graph$G$with exactly$k$vertices that maximizes the number of edges$|E(H)|$. Does anyone know if there exists a polynomial-time ... 0answers 183 views ### Largest “non-disturbing” subset in a graph The definition: The subset of vertices in a graph is called "non-disturbing" if any two vertices from this subset could be connected by a path not passing through other vertices of this subset. ... 1answer 158 views ### Minimum cost cut with discount - what is the complexity? Consider an undirected graph$G=(V,E)$with non-negative edge costs. Given an integer$k$with$0\leq k\leq |E|$, let us call an edge set$C\subseteq E$a$k$-discounted cut, if the following hold:$...
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
I'm interested in the complexity status of the following problem. Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$. Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...