<p>An $NP$-complete structural problem is to decide the existence of odd (even) hole in directed graphs. Anna Lubiw proved the <a href="http://www.sciencedirect.com/science/article/pii/0166218X88901254" rel="nofollow">$NP$-completeness</a> of the above two problems.</p>

<p>A hole is chordless cycle of length greater than three. A cycle in directed graph is chordless if its length is greater than 3 and no two of its vertices are joined by an
edge of the directed graph which does not belong to the cycle.</p>

<p>As for undirected graph, testing for the existence of odd hole passing through a given vertex is <a href="http://www.sciencedirect.com/science/article/pii/0012365X9190098M" rel="nofollow">$NP$-complete</a>. Specifically, the problem is to decide whether a graph contains an induced odd cycle of length greater than three, passing through a prescribed vertex. (Odd hole in a graph is an induced cycle of length at least five). However, the complexity of deciding the existence of odd hole is a long standing open problem (if we drop the requirement of passing through a given vertex). In contrast, the task of finding an even hole in a graph is in $P$.</p>

<p>The structural property of the cycle is the property of being chordless. In directed graph, this is enough for NP hardness (in addition to parity requirement) while in undirected graphs odd parity of the chordless cycle is required for $NP$-completeness.</p>

<p>The importance of detecting odd-hole structure in graphs is highlighted by the recent breakthrough of the <a href="http://en.wikipedia.org/wiki/Strong_perfect_graph_theorem" rel="nofollow">Strong Perfect Graph Theorem</a>. It shows that a graph is
<a href="http://en.wikipedia.org/wiki/Perfect_graph" rel="nofollow">perfect</a> if and only if neither it nor its complementary graph has an odd hole.</p>

CC BY-SA 3.0
2013-11-19T04:28:39.070Z
A cycle is induced cycle if and only if it is chordless cycle (also called hole).
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-19T15:38:27.850Z
Both of your answers sound like the kind of problem I'm looking for, thank you!
G. Bach
CC BY-SA 3.0
2013-11-19T03:34:48.177Z
2013-11-19T12:17:56.477Z
2013-11-19T12:17:56.477Z
Mohammad Al-Turkistany
<p>Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. The problem remains $NP$-complete even for cubic planar graphs. </p>

<p>D. W. Bange, A. E. Barkauskas, and P. J. Slater. <a href="http://books.google.com.sa/books?id=zgHVZdBAezYC&amp;pg=PA189&amp;lpg=PA189&amp;dq=efficient+dominating+sets+in+graphs+bange&amp;source=bl&amp;ots=IU4uL9pxUN&amp;sig=woTBH0AMz2i2X1f4lDAxLh355hU&amp;hl=en&amp;sa=X&amp;ei=h4SLUsaIBqG57AaljoDYDg&amp;safe=on&amp;redir_esc=y#v=onepage&amp;q=efficient%20dominating%20sets%20in%20graphs%20bange&amp;f=false" rel="nofollow">Efficient dominating sets in graphs</a>. Applications of discrete mathematics, Proc. 3rd SIAM Conf., Clemson/South Carolina 1986, 189-199 (1988)., 1988.</p>

CC BY-SA 3.0
2013-11-19T14:59:16.690Z
Other variants of Dominating Set are [Connected Dominating Set](http://en.wikipedia.org/wiki/Connected_dominating_set) and [Independent Dominating Set](http://en.wikipedia.org/wiki/Dominating_set#Independent_domination).
Radu Curticapean
CC BY-SA 3.0
2013-11-19T15:03:01.423Z
@RaduCurticapean But by these variants your do care about the size of the solution.
vb le
CC BY-SA 3.0
2013-11-19T15:07:35.783Z
Yes, I overlooked this.
Radu Curticapean
CC BY-SA 3.0
2013-11-19T14:38:16.350Z
2013-11-19T15:31:40.030Z
2013-11-19T15:31:40.030Z
Mohammad Al-Turkistany
<p>I think there are lot of similar problems. Here are two in vertex version and one in edge version:</p>

<p>1) Does a given graph have an <strong>independent</strong> feedback vertex set? (we don't care about the size of the set). 
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in 
<a href="http://www.sciencedirect.com/science/article/pii/0304397576900591#">Garey, Johnson &amp; Stockmeyer</a>.</p>

<p>2) Does a given graph have a vertex cover <strong>that induces a tree</strong>? (we don't care about the size of the set). 
This <a href="http://www.sciencedirect.com/science/article/pii/S0166218X98001164">paper</a> 
gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.</p>

<p>3) Does a given graph have a dominating edge set <strong>the edges of which form an induced $1$-regular subgraph</strong>? 
(also known as dominating induced matching or efficient edge dominating; the vertex version is given in the 
second answer by Mohammad. 
Again, we don't care about the size of the set). 
This problem is NP-complete (well-known, first proved <a href="http://www.sciencedirect.com/science/article/pii/002001909390084M">here</a>), even for planar bipartite graphs. </p>

<p>The first two problems are particular examples of the problem class called stable-$\pi$: 
Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? 
More NP-complete cases as well as polynomially solvable cases can be found in 
<a href="http://www.sciencedirect.com/science/article/pii/S0166218X98001164">this</a> 
and in <a href="http://www.sciencedirect.com/science/article/pii/S0166218X13003119">this</a> paper 
(and the refs given there) .</p>

CC BY-SA 3.0
2013-11-19T15:37:22.127Z
Those are exactly the kind of problems I'm looking for!
G. Bach
CC BY-SA 3.0
2013-11-19T19:06:29.827Z
@G.Bach Since this exactly answers your question, I suggest you accept the answer and award the bounty.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-19T19:24:49.233Z
@MohammadAl-Turkistany I agree; for some reason, I will only be able to award the bounty in an hour.
G. Bach
CC BY-SA 3.0
2013-11-19T19:27:05.650Z
Thanks for your nice post. I was thinking for a while a long the same lines.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-19T15:01:28.497Z
2013-11-19T18:05:24.623Z
2013-11-19T18:05:24.623Z
vb le
<p>(This question is a bit of a &quot;survey&quot;.)</p>
<p>I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem &quot;feels&quot; quite hard, and I fully expect it to be <span class="math-container">$\mathcal{NP}$</span>-complete. For some reason I'm having a hard time even finding similar problems in literature.</p>
<p>An example of a problem that I would consider comparable to the one I'm dealing with:</p>
<blockquote>
<p>Given a weighted tournament <span class="math-container">$G = (V,E,w)$</span>, is there a feedback arc set in <span class="math-container">$G$</span> the edges of which fulfill the triangle inequality?</p>
</blockquote>
<p>Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.</p>
<p>Have you encountered any decision problems that feel similar to this? Do you remember whether they were <span class="math-container">$\mathcal{NP}$</span>-complete or in <span class="math-container">$\mathcal{P}$</span>? Any and all help appreciated.</p>

CC BY-SA 3.0
2013-11-19T08:50:58.000Z
Perhaps you can explain the structural properties of your problem, there are many experts here that are familiar with NPC proofs and instead of a reference you could get an NPC proof :-)
Marzio De Biasi
CC BY-SA 3.0
2013-11-19T11:31:49.310Z
@MarzioDeBiasi I would very much like to avoid being given a proof to the problem I'm dealing with; it's the first time I'm doing actual research and I'd like to see where I can get on my own :)
G. Bach
CC BY-SA 3.0
2013-11-19T12:51:03.663Z
To me, the question sounds too vague, and it's hard to guess what is really asked. Probably, the question should be made more specific: what you mean by "feel similar to this" and what you mean by "a feedback arc set in G the edges of which fulfill the triangle inequality"; do you want a reference on the feedback arc set problem, or on another problem?
Yoshio Okamoto
CC BY-SA 3.0
2013-11-19T12:56:01.867Z
@YoshioOkamoto I realize that there is some ambiguity in the question, and I hoped the example would clear some of it up. By "feedback arc set in G the edges of which fulfill the triangle inequality" I mean: if $F$ is a feedback arc set and $(a,b)$, $(b,c)$, $(a,c)$ $\in F$, then $w(a,b) + w(b,c) \ge w(a,c)$ has to hold for $F$ to fulfill that property. Previously I only ever encountered problems of the kind $|F| \le k$, but I want $F$ to have a property not related to its cardinality.
G. Bach
CC BY-SA 3.0
2014-02-01T18:05:42.200Z
can someone give a link/ref to "the traditional feedback arc set problem"...?
vzn
<cc.complexity-theory><reference-request><graph-theory><np-complete><survey>
NP complete graph problems about structural properties
G. Bach
# NP complete graph problems about structural properties

(Asked by: username_0 on 2013-11-14)

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

> Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-complete, survey
> **Comments:**
> **username_1**: Perhaps you can explain the structural properties of your problem, there are many experts here that are familiar with NPC proofs and instead of a reference you could get an NPC proof :-)  
> **username_0**: @MarzioDeBiasi I would very much like to avoid being given a proof to the problem I'm dealing with; it's the first time I'm doing actual research and I'd like to see where I can get on my own :)  
> **username_2**: To me, the question sounds too vague, and it's hard to guess what is really asked. Probably, the question should be made more specific: what you mean by "feel similar to this" and what you mean by "a feedback arc set in G the edges of which fulfill the triangle inequality"; do you want a reference on the feedback arc set problem, or on another problem?  
> **username_0**: @YoshioOkamoto I realize that there is some ambiguity in the question, and I hoped the example would clear some of it up. By "feedback arc set in G the edges of which fulfill the triangle inequality" I mean: if $F$ is a feedback arc set and $(a,b)$, $(b,c)$, $(a,c)$ $\in F$, then $w(a,b) + w(b,c) \ge w(a,c)$ has to hold for $F$ to fulfill that property. Previously I only ever encountered problems of the kind $|F| \le k$, but I want $F$ to have a property not related to its cardinality.  
> **username_3**: can someone give a link/ref to "the traditional feedback arc set problem"...?  

---

## 3 answers

### Answer by username_6 on 2013-11-19. Score: 21 | Accepted answer

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1) Does a given graph have an **independent** feedback vertex set? (we don't care about the size of the set).
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in
[Garey, Johnson & Stockmeyer](http://www.sciencedirect.com/science/article/pii/0304397576900591#).

2) Does a given graph have a vertex cover **that induces a tree**? (we don't care about the size of the set).
This [paper](http://www.sciencedirect.com/science/article/pii/S0166218X98001164)
gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3) Does a given graph have a dominating edge set **the edges of which form an induced $1$-regular subgraph**?
(also known as dominating induced matching or efficient edge dominating; the vertex version is given in the
second answer by Mohammad.
Again, we don't care about the size of the set).
This problem is NP-complete (well-known, first proved [here](http://www.sciencedirect.com/science/article/pii/002001909390084M)), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$:
Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$?
More NP-complete cases as well as polynomially solvable cases can be found in
[this](http://www.sciencedirect.com/science/article/pii/S0166218X98001164)
and in [this](http://www.sciencedirect.com/science/article/pii/S0166218X13003119) paper
(and the refs given there) .

> **Comments:**
> **username_0**: Those are exactly the kind of problems I'm looking for!  
> **username_4**: @G.Bach Since this exactly answers your question, I suggest you accept the answer and award the bounty.  
> **username_0**: @MohammadAl-Turkistany I agree; for some reason, I will only be able to award the bounty in an hour.  
> **username_4**: Thanks for your nice post. I was thinking for a while a long the same lines.  

---

### Answer by username_4 on 2013-11-19. Score: 4

An $NP$-complete structural problem is to decide the existence of odd (even) hole in directed graphs. Anna Lubiw proved the [$NP$-completeness](http://www.sciencedirect.com/science/article/pii/0166218X88901254) of the above two problems.

A hole is chordless cycle of length greater than three. A cycle in directed graph is chordless if its length is greater than 3 and no two of its vertices are joined by an
edge of the directed graph which does not belong to the cycle.

As for undirected graph, testing for the existence of odd hole passing through a given vertex is [$NP$-complete](http://www.sciencedirect.com/science/article/pii/0012365X9190098M). Specifically, the problem is to decide whether a graph contains an induced odd cycle of length greater than three, passing through a prescribed vertex. (Odd hole in a graph is an induced cycle of length at least five). However, the complexity of deciding the existence of odd hole is a long standing open problem (if we drop the requirement of passing through a given vertex). In contrast, the task of finding an even hole in a graph is in $P$.

The structural property of the cycle is the property of being chordless. In directed graph, this is enough for NP hardness (in addition to parity requirement) while in undirected graphs odd parity of the chordless cycle is required for $NP$-completeness.

The importance of detecting odd-hole structure in graphs is highlighted by the recent breakthrough of the [Strong Perfect Graph Theorem](http://en.wikipedia.org/wiki/Strong_perfect_graph_theorem). It shows that a graph is
[perfect](http://en.wikipedia.org/wiki/Perfect_graph) if and only if neither it nor its complementary graph has an odd hole.

> **Comments:**
> **username_4**: A cycle is induced cycle if and only if it is chordless cycle (also called hole).  
> **username_0**: Both of your answers sound like the kind of problem I'm looking for, thank you!  

---

### Answer by username_4 on 2013-11-19. Score: 4

Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. The problem remains $NP$-complete even for cubic planar graphs.

D. W. Bange, A. E. Barkauskas, and P. J. Slater. [Efficient dominating sets in graphs](http://books.google.com.sa/books?id=zgHVZdBAezYC&pg=PA189&lpg=PA189&dq=efficient+dominating+sets+in+graphs+bange&source=bl&ots=IU4uL9pxUN&sig=woTBH0AMz2i2X1f4lDAxLh355hU&hl=en&sa=X&ei=h4SLUsaIBqG57AaljoDYDg&safe=on&redir_esc=y#v=onepage&q=efficient%20dominating%20sets%20in%20graphs%20bange&f=false). Applications of discrete mathematics, Proc. 3rd SIAM Conf., Clemson/South Carolina 1986, 189-199 (1988)., 1988.

> **Comments:**
> **username_5**: Other variants of Dominating Set are [Connected Dominating Set](http://en.wikipedia.org/wiki/Connected_dominating_set) and [Independent Dominating Set](http://en.wikipedia.org/wiki/Dominating_set#Independent_domination).  
> **username_6**: @RaduCurticapean But by these variants your do care about the size of the solution.  
> **username_5**: Yes, I overlooked this.  

---

