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

Algorithms on graphs, excluding heuristics.

0
votes
0answers
40 views

Partitioning directed graph

I'm a newbie in the mathematical field of graph theory (started to dive into it only few days ago) but I'm a very fast learner and have deep mathematical background. I'm trying to find/develop an ...
8
votes
1answer
168 views

Could chromatic number be easy to calculate when colouring is hard for some graph class?

Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring Is there any infinite set of graphs $C$ such as: ...
0
votes
0answers
27 views

Minimum cost circulation problem with bounded number of edges

Note: the question was taken from https://cs.stackexchange.com/questions/95479/minimum-cost-circulation-problem-with-bounded-number-of-edges Since there was no answer in that forum (even after ...
2
votes
0answers
141 views

A variant of the Maximum Weight Clique problem

I am trying to solve a problem that I could reduce to the following: Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
3
votes
2answers
140 views

Finding a set which dominates the Minimum Dominating Set

Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$. The dominating set problem is NP-hard, but I am considering ...
4
votes
2answers
116 views

Max cut problem between two connected subgraphs

Let $G$ be a connected graph. Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
-2
votes
1answer
93 views

Finding Cheapest n-Path [closed]

Given a weighted directed acyclic graph, how can I find the cheapest path from an Origin Vertex to a Destination Vertex which ...
2
votes
0answers
37 views

Min cut problem on unbalanced partitions for planar graphs with unit capacity edges

The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
4
votes
1answer
71 views

Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem?

The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability ...
4
votes
1answer
98 views

Fast algorithm to find a maximum connected subgraph of k vertices

Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
3
votes
1answer
105 views

Finding a “lowest” path in a graph

I have an undirected graph $G = (E,V)$, $|V|=n$, where each node $v_i$ has a natural number weight. Think of these weights as heights $h_i$. Given two nodes $s$ and $t$, I'd like to find a lowest ...
4
votes
2answers
134 views

Check if graph stays connected after edge swap

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
3
votes
1answer
117 views

What exactly is Lawler's modification to Yen's algorithm and how does it work?

I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as ...
4
votes
1answer
275 views

Minimum Union-Sum Cost Path

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
1
vote
0answers
46 views

k-center 2.0: A stronger k-center condition

Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$. Note that ...
3
votes
1answer
47 views

Complexity of distributively verifying that the diameter is small

Consider a graph $G=(V,E)$ and an integer parameter $k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
0
votes
0answers
21 views

is there any result on mTSP over highly structured/modular graphs?

I am looking for theoretical results on mTSP (multiple travelling salesmen problem) over structured/modular graphs. If the meaning of "modular" is not clear, think about a graph that represents a ...
0
votes
0answers
19 views

explicit UES for $D$-regular graphs over $N$ vertices through the line graph

First of all observe that if we have $G$, a $D$-regular graph over $N$ vertices that is equipped with a consistent labeling $\ell$ then we can induce a consistent labeling for $L(G)$ the line graph of ...
0
votes
0answers
52 views

How to find cyclic ordering of edges incident on a vertex in a plane graph?

(I asked this on mathse. May be it suits better here) How to find the cyclic ordering of edges incident on a vertex in a plane graph? (ie, in a plane embedding) Of coure we are looking for a ...
6
votes
1answer
146 views

Computing topological sort while keeping edges “short”

Motivation: I want to compute a topological sort order in which the connected vertices are close to each other. Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
0
votes
1answer
50 views

What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?

I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of Counting the number of distinct s-t cuts in a oriented graph It says ...
6
votes
1answer
131 views

Partition edges into edge disjoint walks

Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$. A set of $k$ walks is called a $(S,T)$-walk partition if the walks form a ...
3
votes
0answers
107 views

Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$. The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-...
5
votes
1answer
146 views

“Smallest” path that visits a given set of vertices

I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows: Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ ...
1
vote
1answer
84 views

What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?

I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.
8
votes
2answers
283 views

Counterexample to max-flow algorithms with irrational weights?

It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the ...
13
votes
1answer
315 views

What are the obstructions to extending $L=SL$ to $L=NL$?

Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
0
votes
0answers
58 views

Hypergraph Coloring Complexity

Dear can you help I am confused about the complexity of hypergraph coloring and finding the minimum number of colors Finding the minimum number of colors for strongly coloring a k-uniform hypergraph ...
1
vote
2answers
162 views

Is perfect matching for bipartite graph with no cycles unique?

Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching. My question is if the balanced bipartite graph is also ...
-1
votes
1answer
106 views

Closeness Centrality for Weighted Graphs

In order to determine the Closeness Centrality for a vertex u in a graph, you compute the shortest path between u and all other vertices in the graph. The centrality is then given by: $C(u) = \frac{1}...
0
votes
0answers
45 views

Path Finding: single-source, multi-path, multi-target, and max-depth - approaches and application

Background Definitions (as used here): $\qquad$single-source: for path finding, an algorithm is single-source if it searches from a given node. $\qquad$multi-target: for path finding, an ...
6
votes
0answers
71 views

Complexity of bounded degree full contraction

This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows: Instance: A graph $G$ and two integers $d$ and $k$. Question: Is there a ...
0
votes
0answers
44 views

Find the maximum induced (weighted) subgraph with edge weights greater than some minimum

I have a (fully connected) weighted undirected graph. I want to find a maximal induced subgraph whose edge weights are all above some minimum value. Or, if not a maximal subgraph, then with some ...
5
votes
0answers
162 views

Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
3
votes
0answers
97 views

Graph-related applications of the fast Fourier transform (and other algebraic algorithms)

The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths). However, while the fast Fourier transform algorithm implies several other near-...
15
votes
1answer
388 views

What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and the size of $A$ is ...
2
votes
1answer
108 views

What is the name of this algorithm on direct acyclic graph?

I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit. In ...
0
votes
0answers
28 views

Partitions of regular graphs with upper bounds on bipartition width

Are there efficient graph partitioning algorithms with guaranteed upper bounds on the bipartition width in terms of the total number of vertices of the graph, or another non-spectral quantity (...
1
vote
0answers
89 views

Generalized path cover problem in DAG

Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
-1
votes
1answer
32 views

Maximize graph with k cut edge operations

I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 ...
5
votes
2answers
211 views

Efficient way to generate random planar cubic bipartite graphs

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
5
votes
0answers
57 views

Series-parallel extension of a partial order respecting a given total order

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length. An $O(n^3)$ ...
1
vote
0answers
23 views

Complexity of recognizing generalized graph join

A join of two graphs is the union of both graphs with additional edges such that every vertex of the first graph is connected to every vertex of the second graph. There is a generalization of this, ...
2
votes
1answer
331 views

Maximum difference between two shortest paths

My problem is the following maximization problem: Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two ...
3
votes
2answers
763 views

How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once. For a subset $S$ of nodes and a node $i\in S$, let $D[...
1
vote
0answers
58 views

Counting the number of connected components in a dynamic plane graph

I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{...
2
votes
0answers
76 views

Unbalanced connected partition

Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
6
votes
1answer
260 views

Why isn't the Charikar algorithm for finding the densest subgraph optimal?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different ...
0
votes
0answers
68 views

Number of maximally different DAG's in a digraph?

Given a digraph $\overrightarrow{G}$, I'm interested in extracting all DAGs from $\overrightarrow{G}$ such that: Each DAG's vertices are differently sorted, Each DAG is maximal (adding any extra ...
0
votes
1answer
126 views

How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0? [closed]

Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher ...