Skip to main content

Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
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 ...
Eric_'s user avatar
  • 475
3 votes
2 answers
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 ...
Kye W Shi's user avatar
  • 131
0 votes
0 answers
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. ...
rus9384's user avatar
  • 1,781
5 votes
0 answers
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 ...
Abel's user avatar
  • 51
1 vote
1 answer
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 ...
edamondo's user avatar
  • 111
0 votes
0 answers
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 ...
arg3t's user avatar
  • 1
1 vote
0 answers
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 ...
rus9384's user avatar
  • 1,781
2 votes
1 answer
43 views

Forest of maximal weight edges in weighted graphs

Consider a weighted undirected graph $G=(V,E,\omega)$ and assume for simplicity that all edges have distinct weights. For all $v$ in $V$, we denote by $n(v)$ the unique neighbor of $v$ such that $\...
Matthieu Latapy's user avatar
2 votes
1 answer
32 views

Rule-Based Link Prediction for Social Network

Relevance to Site I believe this question is suitable for the Computer Science Stack Exchange as it pertains to the implementation of a graph algorithm. According to this widely accepted answer, such ...
Jay Gupta's user avatar
-1 votes
0 answers
16 views

Sequencing swaps with constraints

I have an array of N numbers, and M swaps. Each swap has an index i and amount it subtracts from the ith number, and an index j and amount it adds to the jth number. It can only be applied if the ...
sprw121's user avatar
  • 99
0 votes
0 answers
31 views

What is this graph?

I am seeking nomenclature to describe the family of graphs detailed below, and literature about its processing, traversal, costs, etc. Any and all input is welcome, e.g. papers, textbooks, helpful ...
Anti Earth's user avatar
-2 votes
0 answers
24 views

Connecting points in Cluster and chain

I have points in 2D plane which are distributed like cluster in some parts and these cluster are trailed by points from one cluster to another in the form of chain (looks like a chain; can be free ...
Himaghna's user avatar
1 vote
0 answers
38 views

SSA Construction: DFS of CFG vs Traversal of Dominator Tree

According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts Inserting $\phi$ functions. For each existing definition of a variable ...
David Yue's user avatar
  • 143
0 votes
0 answers
22 views

What is the fastest algorithm for generating all non-isomorphic unlabeled free trees for n-vertices, and also for caterpillar trees of n-vertices?

I'm aware of some algorithms for each problem such as the WROM algorithm for unlabeled free trees and the algorithm from this page for all caterpillar trees of n-vertices. However, I haven't been able ...
Ryan Gillies's user avatar
6 votes
1 answer
2k views

Any algorithm to do Huffman encoding without using graphs?

QUESTION Is there any efficient way to encode words into bits, without having to draw the graphs, solely by only using a list of probabilities? EXAMPLE This list of words: Pr('Apple') = 0.5. Pr('...
caveman's user avatar
  • 185
1 vote
0 answers
35 views

Failures of greedy graph coloring

I'm working on an algorithm that, in a certain stage, requires solving a variation of the graph coloring problem. (The vertices are line segments in a plane, and two vertices are connected iff the ...
Draconis's user avatar
  • 7,166
1 vote
0 answers
21 views

Linear time algorithm for computing radius of membership hyper-sphere

We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E. Alongside the ...
moe asal's user avatar
  • 111
0 votes
1 answer
24 views

4COL problem with additional constraint on the size

The task is to prove that that 4-coloring of a graph with additional constraint about number of vertices is NP-complete. Constraint: Each color class should contain at least $ \frac{1}{5}$ of total ...
Abel's user avatar
  • 51
1 vote
1 answer
36 views

How many minimal graphs on $n$ vertices with radius and diameter of 2 are there?

A simple graph is a minimal graph with radius and diameter of 2 if its radius and diameter are 2, and removing any edge would increase its diameter. The question is how many such unlabelled graphs on $...
rus9384's user avatar
  • 1,781
1 vote
1 answer
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 ...
Avi T's user avatar
  • 13
0 votes
1 answer
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 ...
Gouvernathor's user avatar
1 vote
1 answer
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 ...
rus9384's user avatar
  • 1,781
1 vote
1 answer
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 ...
Ellen Spertus's user avatar
-2 votes
1 answer
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. ...
XYJ's user avatar
  • 9
1 vote
0 answers
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 ...
Alvaro Martinez's user avatar
0 votes
0 answers
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 ...
S10000's user avatar
  • 101
4 votes
3 answers
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 ...
Lisa E.'s user avatar
  • 555
1 vote
0 answers
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 ...
Dan's user avatar
  • 61
1 vote
1 answer
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 ...
aioobe's user avatar
  • 229
2 votes
1 answer
76 views

Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq ...
HonestSJ's user avatar
2 votes
0 answers
31 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,781
1 vote
1 answer
79 views

MSOL for a vertex-cover enlargement problem

Consider the following problem. 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'|\le k$, and any subset $V'\...
Lisa E.'s user avatar
  • 555
0 votes
0 answers
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 ...
Lisa E.'s user avatar
  • 555
1 vote
1 answer
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 ...
Caroline's user avatar
2 votes
1 answer
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 ...
olivarb's user avatar
  • 121
3 votes
1 answer
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....
Lisa E.'s user avatar
  • 555
0 votes
1 answer
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 ...
Stephen Stone's user avatar
1 vote
2 answers
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 ...
Sgg8's user avatar
  • 111
2 votes
1 answer
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 ...
Sander's user avatar
  • 225
1 vote
0 answers
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?
Lisa E.'s user avatar
  • 555
-2 votes
1 answer
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?
user170509's user avatar
0 votes
1 answer
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?
Shay's user avatar
  • 113
2 votes
0 answers
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?
Lisa E.'s user avatar
  • 555
3 votes
4 answers
440 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
Lisa E.'s user avatar
  • 555
2 votes
1 answer
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 ...
27rabbit's user avatar
3 votes
1 answer
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 ...
Mařík Savenko's user avatar
0 votes
0 answers
36 views

Graph with an exponential number of paths

I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.: $G$ is undirected $G=(V,E)$ $v_0,v_1\in V$ $|V|=n$ There are $2^n$ paths between $v_0$ and $v_1$ I would like to prove that $F\notin ...
Benicio Agüero's user avatar
5 votes
0 answers
100 views

Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem: Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
InfiniteSnow's user avatar
1 vote
0 answers
22 views

Global minimum weighted vertext cut for undirected graphs

Given an undirected graph with vertex weights, there any algorithm for finding the global minimum vertex cut that partitions the graph into two components? I can transform the graph to directed one ...
tr244's user avatar
  • 11
0 votes
0 answers
9 views

Managing hashing overlaps (building a heuristic for the edge of a 3x3x3)

I'm trying to build a 3x3x3 solver for a school project. I got inspired by Ben Botto's solver, which you can find here. Such as Ben does with his solver, I'd like to implement Korf's heuristic ...
AlioTheCat's user avatar

1
2 3 4 5
100