Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,967 questions
Filter by
Sorted by
Tagged with
1 vote
10 views

Classical matrix multiplication via Min-Plus matrix multiplication

Just a thought I had in mind. I can use classical matrix multiplication to compute min-plus matrix multiplication. Generally speaking, considering $(n+1)^{a_{i,j}}$ for each entry and then taking the ...
• 475
52 views

Vertex cover approximation: what's wrong with max-degree heuristic?

For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
• 131
13 views

Why is it not possible to recognize a self-complementary graph just by searching for a self-complementary graph on $8$ vertices?

From the paper by Gibbs (1974) it is known that every self-complementary graph on $4n$ vertices has $n$ disjoint induced $P_4$ subgraphs. Let's call the collection of these subgraphs a $P_4$ cover. ...
• 1,781
85 views

Polynomial time algorithms for graphs and cycles

For a given undirected graph $G$ , let $c(G)$ denote the length of the longest cycle in $G$ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
• 51
1 vote
28 views

Livout analysis of control flow graph of a program

I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc ...
• 111
13 views

Calculating the most influential set of source nodes on a target node when a source node's signal is propagated

I am mainly posting for guidance, as I don't know where to start looking in order to solve the following problem: Given a directed graph G with edge weights between 0 and 1. As well as a set of ...
1 vote
11 views

Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?

It is known that decision variants of these problems on perfect graphs are decidable in polynomial time. But is counting the number of maximum cliques or optimal colorings $\#\mathsf P$-hard on ...
• 1,781
43 views

• 1,781
1 vote
29 views

Extract dominant value per column with single value per row in a matrix

Given a matrix $A \in \mathbb{R}_{+}^{n \times m}$ where $m \geq n$. I want to convert it into a form where there is a single $1$ per row yet no more than a single $1$ per column. The logic is convert ...
• 13
31 views

Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it. I have an ordered sequence of groups, each with an integer attributed to it, such that ...
• 101
1 vote
50 views

Is this graph grouping problem $\mathsf{NP}$-hard?

Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property: If any pair of vertices is connected with an edge, these two vertices ...
• 1,781
1 vote
27 views

Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
• 1,570
38 views

$O(|V||E|)$ algorithm for finding all the cut vertices in a connected graph

Given a connected graph $G = (V, E)$, how to find all the cut vertices in $G$ in $O(|V||E|)$ time? I have considered some algorithms for finding all cut vertices in a connected graph as follows. ...
• 9
1 vote
30 views

Bron-Kerbosch algorithm for finding cliques missing a few edges?

The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices). Let $t$ be a positive ...
26 views

Kruskal's algorithm including an edge

I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
• 101
229 views

MSOL and Courcelle's theorem for maximum clique

The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed. The traditional proof is by a dynamic programming ...
• 555
1 vote
33 views

Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
• 61
1 vote
49 views

Find the transitive closure but with a twist

Situation I have a set of set of elements V, and relations over V: a R b: "a is related to b" (reflexive and symmetrical) a N b: "a is not related to b" (anti-reflexive and ...
• 229
76 views

• 555
27 views

Adding edges to enlarge vertex cover

Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
• 555
1 vote
46 views

BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
• 11
66 views

Find hierarchical clustering of documents

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)? My ...
• 121
370 views

Easy/hard NP-hard problems on perfect graphs

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph....
• 555
49 views

Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $G = (V, E)$ where a vertex $v \in V$ is designated as the center if it is connected to every other vertex $u \in V$, such that both $uv$ and $vu$ are present in $E$. A ...
1 vote
51 views

Shortest path between two nodes with time-dependent edge weights

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
• 111
31 views

Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M$ such that the rank of the matrix $$A = \sum_{m \in N}m$$ is minimal. I am wondering if anyone have seen ...
• 225
1 vote
36 views

MSOL framing of max-flow probem

Given a graph $G=(V,E)$ with edge capacities $c_e$ for each $e\in E$, a source $s\in V$ and destination $t\in V$, how do I frame the max-flow problem in MSOL?
• 555
33 views

Implementation of planar graph max cut

http://comopt.ifi.uni-heidelberg.de/conferences/aussois2009/slides/pardella.pdf Can you simply implement or pseudo code the content of this slide as a whole?
22 views

True/False: Given an edge $(u,v)$: no path exists from $u$ to $v$ in the residual graph w.r.t a max flow $\iff$ $(u,v)$ crosses some minimum cut

I was asked to show if this is true or false. I believe it is true, but proving it seems difficult. Is it true and how might one show this?
• 113
22 views

Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
• 555
440 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
• 555
41 views

Why there is no definition of cut vertex in directed graph?

We know cut vertex is an important definition in undirected graph, indicating a vertex which when removed, the number of connected components would increase. And we also have an efficient algorithm ...
• 23
51 views

Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
36 views

1 vote