Tag Info

Hot answers tagged graph-theory

3

Your problem is NP-hard. There is a reduction from Independent Set to its decision version. Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\{s,t\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\{1,2,3\}$, then $V'=\{v_{12},v_{23},v_{13}\}$. Then we construct ...

2

Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.

2

The problem statement needs to be specified more precisely to be meaningful. If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-...

2

I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$. The initial state has the empty set $\emptyset$, and it can transition to any state ...

2

Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics. The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even). In the bipartite case, however,...

1

While your description of the problem is not super clear. I can guess that you're looking at a maximum bipartite matching problem. Which by the way, can also be viewed as a degenerate case of maxflow problem. Both problems are classic, you should have no problem finding resources on them. For example, this.

1

The minimum cost perfect matching problem is formally defined as an optimization problem where: The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$. Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $... 1 Use depth-first search, or breadth-first search, or any other graph search algorithm. You don't need Tarjan's algorithm. 1 You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a$K_{101}$? 1 The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging. Kahn and Saks showed that partially sorted lists can be sorted in$O(\log M)$, where$M\$ is the number of possible ...

Only top voted, non community-wiki answers of a minimum length are eligible