# Tagged Questions

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

0answers
36 views

0answers
38 views

### Does there exist any distributed algorithms for the Minimum Feedback Arc Set Problem

I am wondering if there are any known distributed algorithms for the Minimum Feedback Arc Set Problem. Exact solutions, approximation algorithms, and heuristic approaches all welcome.
0answers
32 views
+50

### 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 ...
0answers
39 views

### Are there any heuristics that works solely on graphs?

I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work ...
0answers
52 views

### Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
1answer
68 views

1answer
163 views

### Graph planarity testing via adjacency matrix

I have looked at several efficient graph planarity algorithms which rely on computing and traversing DFS trees (that add one vertex/edge/path at a time). I am looking for graph planarity algorithms ...
0answers
402 views

### Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?

Last year I spent some time trying to prove or disprove the following: Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is ...
1answer
272 views

1answer
216 views

1answer
193 views

### Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$,...
1answer
84 views

### Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or non-...
1answer
247 views

### Is the proceedings of WG 2015 published?

Within theoretical computer science, the "Workshop on Graph-Theoretic Concepts in Computer Science (WG)" is one of the main specialized venues for publication of papers dealing with graph theory. It's ...
0answers
53 views

### About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
1answer
225 views

### Enumerating all (super)orientations of an undirected graph

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in ...
0answers
80 views

### Graph partition with weighted vertices and edges

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
0answers
112 views

### Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs

In the 1996 paper "Short Paths in Expander Graphs" by Kleinberg and Rubinfeld, the authors show a randomized polynomial-time algorithm for finding an embedding of a graph $H$ into a graph $G$, if $G$ ...
0answers
142 views

### Machine learning algorithms on hypergrap models

Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two ...
1answer
124 views

### Tree-decomposition with clique interfaces

Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that: For every edge $\{v_1,v_2\} \in E$, ...
1answer
118 views

0answers
231 views

### Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...